Tävlingsprogrammering/Uppgifter/Springoalla

Springoalla

Springoalla älskar att löpträna. Totalt känner hon till n löpspår och hon vet exakt hur lång tid det tar för henne att springa det spåret och sedan tillbaka. Den första gången hon springer på ett nytt spår, så lär hon känna spåret lite bättre. Närmare bestämt lär hon sig var i spåret hon kommit halvvägs, och har då möjlighet att springa tillbaka efter halva spåret. Då blir löptiden halverad. T.ex. kan hon springa ett halvt 20-minutersspår på 10 minuter, men bara efter att hon redan sprungit hela spåret en gång.

Springoalla vill löpträna i minst t minuter men hon är också noggrann med att inte träna för länge. Givet tiderna för varje spår, beräkna hur lång tid t_s hon minst måste springa. Talet t_s ska alltså vara så litet som möjligt men uppfylla t_s≥t. Om det finns flera sätt att springa ts minuter vill Springoalla springa så litet antal sträckor n_s som möjligt, där man räknar varje gång hon springer bort från utgångspunkten som en sträcka, oavsett om det är ett helt eller halvt spår. Finns det flera lösningar med samma t_s och n_s kan du ange vilken som helst av dem.

Indata

På första raden står två heltal n och t, där 1≤n≤1000 är antalet löpbanor och 1≤t≤100000 är tiden som Springoalla vill löpträna. På andra raden står n stycken heltal l_i, där 1≤l_i≤40000 kommer vara ett jämnt heltal och är antalet minuter det tar att springa löpspår i. Talet t behöver däremot inte vara jämnt.

Utdata

Första utdataraden ska innehålla de två heltalen t_s och n_s: den tid Springoalla måste springa respektive hur många sträckor hon totalt springer. Därefter ska en rad skrivas med n heltal, där det i:te heltalet anger hur många minuter Springoalla sprang på spår i.

Exempel 1

3 23
10 8 14

ska ge svaret

23 3
15 8 0

Exempel 2

3 23
8 12 14

ska ge svaret

24 2
0 24 0

Exempel 3

1 3
2

ska ge svaret

3 2
3

Exempel 4

1 7
4

ska ge svaret

8 2
8

Lösning

Den som löst många gamla programmeringsuppgifter lägger genast märke till likheten med Knapsack-problemet, som kan lösas med dynamisk programmering. Det är dock inte helt uppenbart hur man ska hantera möjligheten att springa halva spår, och det finns givetvis många sätt att göra detta.

Vill man komma fram till det klassiska Knapsack-problemet kan man notera att man aldrig vill springa mer än en runda på ett visst halvspår, och eftersom kravet att få springa den halvrundan är minst en helrunda kan man helt enkelt skapa ett nytt spår med längden 1.5 l_i för varje spår i. Man måste dock komma ihåg att dessa extraspår ska räknas som två vanliga när man optimerar n_s.

Eftersom man för att skriva ut svaret behöver kunna återskapa vilka rundor man sprungit, måste man spara denna information under Knapsack-optimeringen. Det lättaste sättet är att, samtidigt som man markerar att man hittat den hittills bästa lösningen (d.v.s. minst antal rundor) att nå en viss tid, också spara indexet på det senaste spår man använde för att komma dit. För att efteråt återskapa hela listan med spår vandrar man då bara bakåt i tiden från t_s , ett spår i taget tills man når tiden 0.

Lösning i C:

#include <stdio.h>
#define NONE 1000000
  
int main() {
  int n,T,t[2000], W[160001], B[160001],m[1000],i,j,k;
  scanf("%d %d\n", &n, &T);
  for(i=0;i<n;i++) {
      scanf("%d", &t[i]);
      t[i+n]=t[i]*3/2;   //Lägg till extraspår med längd 1.5*t[i] 
  }
  for(i=0;i<=T+60000;i++) W[i]=NONE;    // W[t] innehåller minimalt antal spår för att nå tiden t
  W[0]=0;
  for(i=0;i<2*n;i++) {      //Loopa över alla spår 
    k=(i>=n)?2:1;      //Om det är ett av extraspåren ska det räknas som två spår 
    for(j=0;j<=T;j++) {       //Loopa över alla tidpunkter och spring spåret i 
        if(W[j]+k<W[j+t[i]]) {    //Om detta ger den bästa lösningen för en tidpunkt...     
           W[j+t[i]]=W[j]+k;    //.... så spara den bästa lösningen...   
           B[j+t[i]]=i;         //... och markera vilket spår vi tagit för att nå hit.   
        }   
    }   
  }
  for(i=T;W[i]==NONE;i++) ;    //Loopa fram till första bästa tid som går att nå
  printf("%d %d\n", i, W[i]);   
  for(j=0;j<n;j++) m[j]=0;  
  while(i>0) {
    m[B[i]%n]+=t[B[i]];         //Samla ihop sprungna minuter i varje spår
    i-=t[B[i]];                 //Återskapa hela listan av valda spår genom att vandra bakåt i tiden
  }
  for(j=0;j<n;j++) printf("%d ",m[j]);
  printf("\n");
  return 0;
}