Tävlingsprogrammering/Uppgifter/Lasta färjan
Lasta färjan
En bilfärja ska lastas med bilar, och en samling bilar står på kö för att komma med färjan. Tiden mellan turerna är väldigt lång, och därför är det viktigt för de resande att så många bilar som möjligt kan komma med färjan vid en sådan tur. Bolaget Kass Sjöfart AB (som driver bilfärjan) har på sistone mottagit ett stort antal klagobrev från en organisation som kallar sig Arga Unga Algoritmiker som menar att packningen av bilar på färjan är "dålig", "suboptimal", "heuristisk" och "ohållbar". Bolagets verkställande direktör Ernst E. Kass bekräftar att man slarvat vid packningen av färjan, och går nu ut med ett uttalande om att man hädanefter alltid kommer att packa färjan så att så många bilar som möjligt kommer med. Hur man ska lyckas med det har Ernst inte velat svara på, men ryktet säger att man bett den svenska Programmeringsolympiaden om hjälp.
Bilfärjan har fyra filer, där varje fil har en viss längd i meter, och alla filer är lika långa. En samling bilar står på kö för att få åka ombord på färjan, och bilarna kommer att åka på färjan i den ordning som de står i kön. Personalen på färjan kan dock välja vilken fil som en viss bil ska åka in i (givet att den får plats). När en bil inte längre får plats i någon av filerna så anses färjan vara fullastad (man hoppar alltså inte över bilar). Dessutom är det viktigt att det är minst en meters avstånd mellan varje par av bilar som står intill varandra i samma fil (ifall det skulle börja gunga, och bilarna sätts i rörelse).
Du kommer att få veta hur lång färjan är, och vilka bilar som står i kön. Din uppgift är att hjälpa färjepersonalen med att räkna ut hur många bilar man som mest kan lasta, om man är smart när man väljer fil åt bilarna.
Indata
På första raden i indata står ett heltal N, antal bilar. Antalet bilar i kön är max 200. På andra raden i indata står ett heltal L, längden på filerna. Filerna är inte längre än 60 meter. Sedan följer N heltal på en rad (separerade av mellanslag), där varje heltal beskriver längden på en bil. Bilarna är minst 1 meter långa och högst 10 meter långa och samtidigt högst L. Bilarna först i denna sekvens är de som står först i kön.
Delpoäng: För 30% av poängen gäller att N≤20 och L≤40.
Utdata
Utdata ska bestå av ett enda heltal: det högsta antal bilar som får plats på färjan.
Exempel
Körningsexempel 1
10 5 2 1 2 5 1 1 2 1 1 2 Svar: 8
Körningsexempel 2
6 1 1 1 1 1 1 1 Svar: 4
Körningsexempel 3
10 10 1 2 7 2 5 9 10 9 4 3 Svar: 7
Lösning
redigeraPå den här uppgiften fanns det en del poäng att plocka med en bra girig lösning. Dock ska man förstås sträva efter att lösa problemet korrekt, så läs igenom det här avsnittet och skicka gärna in en ny, korrekt lösning (träning är bra!).
Delpoäng (30p)
redigeraFör att samla in den första delpoängen så räckte det med att skriva en någorlunda effektiv totalsökning. Dvs prova alla möjliga val av filar för bilarna, och avbryt sökningen när du kommer till ett tillstånd som är sämre än tidigare.
Full poäng: Dynamisk programmering
redigeraFör att lösa uppgiften korrekt behövs några insikter. Då det inte är uppenbart hur det kan finnas en optimal girig strategi så kan det vara bra att tänka efter om man kan dela upp problemet i delproblem, dvs applicera dynamisk programmering.
Låt oss fundera på vilka delproblem som finns. Vi vet att antalet bilar i kön är max 200 och att antalet olika metertal som kan vara fyllda i vardera fil är max 60. Innan du läser vidare så ber jag dig att fundera på om du kan se några delproblem till detta problem, sådana att mängden sådana delproblem är mindre än ~20 miljoner (så att vi kan spara svaren för dem i minnet). I nästa stycke kommer nämligen svaret.
Ett första försök
redigeraEtt uppenbart delproblem som vi kan finna är att vi löser problemet för parametrarna (nuvarande bil i kön, antal meter packade i fil 1, antal meter packade i fil 2, ..., antal meter packade i fil 4).
En implementation av idén ovan skulle se ut på ungefär följande vis (väldigt grovt skissat):
int dp(int N, int f1, int f2, int f3, int f4) {
# kolla först om vi har räknat ut detta tillstånd tidigare, i så fall returnera svaret
if tabell[N,f1,f2,f3,f4]:
return tabell[N,f1,f2,f3,f4]
om bil[N] inte får plats i någon av köerna:
return N # vi lyckades packa N bilar
annars:
# prova att stoppa in bil[N] i alla köer den får plats i,
# returnera maximum av de rekursiva anropen
svar = -infinity
if f1 + bil[N] + (f1?1:0) <= L :
svar = max(svar,N+1,f1+bil[N],f2,f3,f4)
# ... osv ...
}
Denna funktion skulle kunna anropas för 200 (maxantalet bilar) * 60^4 (60 är maximal fillängd) olika värden. Vi observerar att 200 * (60^4) = 2 592 000 000, och blir omedelbart väldigt ledsna, det är ju alldeles för stort.
Godkänd lösning
redigeraMen behöver vi verkligen alla fem parametrar för att särskilja ett sådant tillstånd? Tänk efter en stund innan du läser vidare. Svaret är förstås: nej! Vi kan välja att kasta bort antingen en faktor 200, eller en faktor 60.
Låt oss börja med att beskriva hur vi kastar bort en faktor 60. Anta att du vet hur många bilar du packat (faktorn N till funktionen), och hur mycket du packat i 3 av filerna (vi utesluter en fil). Då är det enkelt att räkna ut hur mycket som är packat i den fjärde filen, eller hur? Då får vi alltså en tillståndsrymd av storlek 200 * (60^3) = 43 200 000, en klart rimligare siffra.
(Faktum är att lösningen tar L^4 tid, trots att den tar O(N * L^3) minne. Detta eftersom när vi fixerat de tre första längderna finns det högst L fall för längden ändå. )
Exempel på N*L^3-lösning i C++, som använder sig av insikten ovan:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, l;
int lengths[200];
int lengthsum[201];
int dp[62][62][62][200];
int go(int a, int b, int c, int at){
if(dp[a][b][c][at] != -1) return dp[a][b][c][at];
int d = lengthsum[at] - a - b - c;
int ans = 0;
for(int i = 0; i<4; i++){
int xs[] = {l - a, l - b, l - c, l - d};
if(xs[i] < lengths[at]) continue;
xs[i] -= lengths[at];
sort(xs, xs+4);
ans = max(ans, go(l-xs[0], l-xs[1], l-xs[2], at+1)+1);
}
return dp[a][b][c][at] = ans;
}
int main(){
memset(dp, -1, sizeof(dp));
scanf("%d%d", &n, &l);
l++;
for(int i = 0; i<n; i++){
scanf("%d", lengths + i);
lengths[i]++;
lengthsum[i+1] = lengthsum[i] + lengths[i];
}
printf("%d\n", go(0,0,0,0));
}
L^4-lösning i Go (av Anton Fors Hurdén):
package main
import "fmt"
var m [60][62][62][62]int
var q [200]int
func pack(a, b, c, d, n int) int {
if m[a][b][c][d] != 0 {
return m[a][b][c][d]
}
p := n
if a >= q[n] {
p = pack(a-q[n], b, c, d, n+1)
}
if b >= q[n] && b != a {
if pp := pack(a, b-q[n], c, d, n+1); pp > p {
p = pp
}
}
if c >= q[n] && c != a && c != b {
if pp := pack(a, b, c-q[n], d, n+1); pp > p {
p = pp
}
}
if d >= q[n] && d != a && d != b && d != c {
if pp := pack(a, b, c, d-q[n], n+1); pp > p {
p = pp
}
}
m[a][b][c][d] = p
return p
}
func main() {
var n, l int
fmt.Scan(&n, &l)
l++
for i := 0; i < n; i++ {
fmt.Scan(&q[i])
q[i]++
}
fmt.Println(pack(l-q[0], l, l, l, 1))
}
Samma lösning som ovan, fast skriven i C (av Anton Fors Hurdén):
#include <stdio.h>
int m[60][62][62][62], q[200];
int pack(int a, int b, int c, int d, int n) {
int p = n, r;
if (m[a][b][c][d]) return m[a][b][c][d];
a >= q[n] && (p = pack(a - q[n], b, c, d, n + 1));
b >= q[n] && b != a && (r = pack(a, b - q[n], c, d, n + 1)) > p && (p = r);
c >= q[n] && c != a && c != b && (r = pack(a, b, c - q[n], d, n + 1)) > p && (p = r);
d >= q[n] && d != a && d != b && d != c && (r = pack(a, b, c, d - q[n], n + 1)) > p && (p = r);
return m[a][b][c][d] = p;
}
int main() {
int n, l, i;
scanf("%d%d", &n, &l);
l++;
for (i = 0; i < n; i++) {
scanf("%d", &q[i]);
q[i]++;
}
printf("%d\n", pack(l - q[0], l, l, l, 1));
}
Super smart O(N) lösning
redigera- Den här lösningen fungerar inte för många invärden. Exempelvis en färjelängd på 26 meter och en kö av lastbilar på 20 meter. Rätt svar är 4 men denna ger 5.
Det finns också en väldigt intressant lösning som löser problemet i O(N) tid (i sämsta fall). Man kan nämligen inse att problemet egentligen frågar efter summan av alla bilars längd + säkerhetsavstånden som är så nära de fyra längdernas sammanlagda längd. Alltså kan vi i linjär tid addera ihop varje bilslängd + 1 (säkerhetsavståndet var 1 meter). Sedan tar vi summan minus fyra, eftersom den första bilen i varje längd inte behöver något säkerhetsavstånd. Precis innan summan överstiger filernas totala längd, alltså L*4, så har vi lastat så många bilar som det bara går. Antalet bilar vi har lastat är antalet bilar vi har adderat. Den här lösningen fungerar eftersom uppgiften inte frågar hur vi ska placera bilarna utan bara efter antalet bilar.
Lösning av Andreas Wallström (Alexander Bladh och alla andra som har 0.00s har uppenbarligen löst uppgiften på samma sätt):
#include <iostream>
int main() {
int N, L, n, sum = -4, len = 0; // Tar -4 från början (de fyra första bilarna har inget säkerhetsavstånd)
std::cin >> N >> L;
while(!(std::cin >> n).eof()) // Läs in tal för tal
if((sum += n + 1) > L*4) break; // Om summan överstiger L*4 så har vi funnit svaret, avbryt
else len++; // Antalet bilar som får plats, öka med ett
std::cout << len;
}