Tävlingsprogrammering/Uppgifter/Gourmeten

Gourmeten

Den franska gourmeten Frank är en väl respekterad gourmet; hans yrke är att gå runt till olika restauranger, äta av deras mat och ge sitt omdöme om restaurangen. Men han bär på en hemlighet: han är egentligen bara intresserad av att äta så mycket som möjligt och i vilken ordning som helst!

Frank förstår dock att en äkta gourmet inte kan äta hur som helst, t.ex. börja med sin dessert och avsluta med en sallad. Därför ber han om din hjälp att ta fram en lista med alla olika sätt att ordna maträtterna under en bjudning, så han kan välja ut den ordning som är finast.

På bjudningen har Frank M minuter på sig att äta. Restaurangen bjuder på N olika rätter som han kan äta hur många portioner som helst av. Varje rätt tar ett visst givet antal minuter att äta. Frank vill äta kontinuerligt under alla de M minuter han har på sig, och han vill hinna äta klart alla rätter han påbörjat. Han vill aldrig påbörja en ny rätt innan han ätit färdigt den förra. Din uppgift är att skriva ett program som räknar ut på hur många olika sätt han kan lägga upp middagen, givet dessa restriktioner.

Indata

På första raden står ett heltal M, antalet minuter, där 1 ≤ M ≤ 1000. På andra raden står ett heltal N, antalet rätter, där 1 ≤ N ≤ 30. Därefter följer N rader med ett heltal T[i] på varje rad, tiden det tar att äta varje rätt, där 1 ≤ T[i] ≤ 200.

Utdata

Programmet ska skriva ut antalet möjliga sätt Frank kan äta under exakt M minuter. Svaret kommer alltid understiga 2 miljarder.

Tips: I 60% av testfallen kommer svaret att vara under 2 miljoner, så även en icke-optimal lösning kan ge mycket poäng.

Exempel 1: Indata

10
2
7
3

Exempel 1: Utdata

2

Förklaring: Frank ska alltså äta under 10 minuter och han har 2 rätter att välja på, t.ex. sallad (tar 3 minuter att äta), och paj (7 minuter). Det finns bara två sätt att äta på: först paj sen sallad eller tvärtom. Äter han bara sallad kommer han antingen att bli klar för snabbt (3 portioner = 9 minuter) eller för sent (4 portioner = 12 minuter).

Exempel 2: Indata

12
6
1
3
3
5
6
12

Exempel 2: Utdata

498

Lösning

Uppgiften är i stort sett identisk med plankan som på PO:s introsida används som ett exempel på en uppgift som kan lösas rekursivt. Men som det också står där finns det en mycket mer effektiv lösning, dynamisk programmering, som behövs för att få full poäng på gourmeten.

Låt oss först skriva om den rekursiva lösningen på plankan så den stämmer med gourmeten (vi passar också på att låta den rekursiva funktionen returnera antalet lösningar istället för att använda en räknevariabel). Funktionen numways räknar alltså ut hur många sätt det finns att äta på r minuter genom att helt enkelt loopa över alla möjliga maträtter p och summera antalet sätt man kan äta på r-t[p] minuter. Och detta kan ju beräknas genom att funktionen numways anropar sig själv, d.v.s. man använder en s.k. rekursiv funktion, Man får bara se upp så att rekursionen tar slut någon gång, man behöver alltså några basfall, som i vårt fall då r=0 (det finns bara ett sätt att äta på 0 minuter) eller r<0 (omöjligt att äta).

#include <stdio.h>

int t[30],N,M;

int numways(int r) {  //r är hur lång tid som återstår
  int p,sum;
  if(r < 0) return 0;            //Ingen lösning
  if(r == 0) return 1;          //Det gick jämnt upp. En lösning hittad.
  sum=0;
  for(p=0;p<N;p++) sum+=numways(r-t[p]);       //Testa varje maträtt och rekursera!
  return sum;
}

int main() {
  int i;
  scanf("%d %d", &M, &N);
  for(i=0;i<N;i++) scanf("%d", &t[i]);
  printf("%d\n", numways(M));
  return 0;
}

Men om det finns miljarder sätt att äta på så kommer ju funktionen anropas miljarder gånger, varav miljontals gånger med exempelvis argumentet 8, eftersom det ofta finns massor av olika sätt som det rekursiva schemat kan komma ner till 8 kvarvarande minuter utgående från ett stort antal minuter.

Detta är förstås helt onödigt! Om vi har räknat ut hur många sätt det finns att äta på 8 minuter så gäller det ju även nästa gång, så vi kan spara det resultatet i en tabell och endast låta funktionen göra sin uträkning om resultatet inte finns sparat i tabellen. Eftersom det högsta antalet minuter är 1000, så behövs det högst 1000 uträkningar. D.v.s. programmet går ungefär en miljon gånger snabbare, och det enda som krävs är fyra rader tillägg i koden (rödfärgat nedan).

Detta är ett enkelt exempel på dynamisk programmering, som helt enkelt innebär att man sparar redan uträknade resultat i en array eller i mer komplicerade fall en flerdimensionell matris för att kunna återanvända dem.

#include <stdio.h>

int nw[1000], t[30],N,M;

int numways(int r) {  //r är hur lång tid som återstår
  int p,sum;
  if(r < 0) return 0;            //Ingen lösning
  if(r == 0) return 1;          //Det gick jämnt upp. En lösning hittad.
  if(nw[r]!=-1) return nw[r];           //Den magiska raden
  sum=0;
  for(p=0;p<N;p++) sum+=numways(r-t[p]);     //Testa varje maträtt och rekursera!
  nw[r]=sum;
  return sum;
}

int main() {
  int i;
  scanf("%d %d", &M, &N);
  for(i=0;i<N;i++) scanf("%d", &t[i]);
  for(i=0;i<=M;i++) nw[i]=-1;               //Låt -1 betyda att vi inte räknat ut värdet ännu 
  printf("%d\n", numways(M));
  return 0;
}