Tävlingsprogrammering/Uppgifter/Pärlband

Pärlband (PO-onlinekvalet 2008)

Du har en uppsättning pärlor i olika färger som du vill rada upp längs ett snöre. För att det ska se snyggt ut måste varje grupp av tre intilliggande pärlor bestå av tre olika färger. Skriv ett program som, givet antalet pärlor av varje färg, beräknar på hur många olika sätt pärlorna kan placeras på snöret. Alla pärlor måste användas.

Indata

På första raden står ett heltal: antalet olika färger på pärlorna (3 ≤ n ≤ 5). Därefter följer en rad med n heltal: antalet pärlor av varje färg (mellan 1 och 8).

Utdata

Programmet ska skriva ut en rad med ett heltal: antalet olika sätt pärlorna kan placeras på snöret. Svaret ryms alltid i ett 64-bitars heltal (long long i C++ respektive long i Java).

Exempel: Indata

4
4 3 2 1

Exempel: Utdata

10

Lösning

Det är naturligt att försöka attackera detta problem med rekursion. Vi gör helt enkelt en funktion som returnerar antalet möjliga pärlband givet hur många pärlor av varje färg vi har kvar (nästan). I funktionen pröva vi att tilldela den först pärlan i bandet de olika färger vi har att tillgå. För varje försök anropar vi rekursivt med en uppdaterad färg-parameter (vi räknar bort den färg som vi lät den första pärlan ha). Det rekursiva anropet löser ett mindre problem (kortare pärlband), så de rekursiva anropen kommer att terminera. Allt vi behöver göra är att summera ihop antalet sätt att sätta ihop de kortare pärlbanden, så har vi lösningen på ursprungsproblemet.

Det finns dock två problem. Det första är uppenbart - vissa färger får inte väljas vid vissa tillfällen. När en färg väljs ut, får den färgen inte finnas vid någon av de två tidigare positionerna. Den rekursiva funktionen måste därför även ta två parametrar som innehåller de senaste två valda färgerna, och se till att inte välja någon av dessa.

Det andra problemet är att svaret kan bli väldigt stort, och att räkna alla lösningar en i taget skulle ta alldeles för lång tid. Lösningen på det är att använda en teknik som kallas "memoization" (i princip detsamma som cachning). Vår rekursiva funktion har inga sidoeffekter (dvs varje gång den anropas med samma parameteruppsättning kommer den att returnera samma värde), och har en begränsad domänmängd (9^5 * 5 * 5 möjliga inputparametrar). Vi kan därför skapa en cache och se till så att funktionen aldrig evalueras mer än 9^5 * 5 * 5 gånger.

 using System;
 using System.Collections.Generic;
 using System.IO;
 
 public class Uppgift5
 {
     public static void Main(string[] args)
     {
         Solve(new StreamReader("parlband1.in"), Console.Out);
     }
      
     private long[,,] memo;       {{komm|1=// 0 = ocachat, x = returnera x-1}}
 
     public static void Solve(TextReader tr, TextWriter tw)
     {
         int n = int.Parse(tr.ReadLine());
         int[] count = Array.ConvertAll<string, int>(tr.ReadLine().Split(' '), int.Parse);
         int max = 1;
         for (int i = 0; i < n; i++)
             max *= 11;
 
         memo = new long[n+1,n+1,max];         
         long cnt = go(n, n, count);
         tw.WriteLine(cnt);
     }
 
     static int Encode(IEnumerable<int> count)
     {
         int hc = 0;
         foreach (int x in count)
             hc = hc*11 + x;
         return hc;
     }
 
     private static long go(int last1, int last2, int[] count)
     {
         int hc = Encode(count);      {{komm|// Skapa en cache-nyckel av indataparametrarna}}
         if (hc == 0)
             return 1;
         {{komm|// Har vi cachat resultet av funktionen?}}
         if (memo[last1, last2, hc] != 0)
             return memo[last1, last2, hc]-1;
         
         {{komm|// Beräkna värdet att funktionen}}
         long sum = 0;
         for (int i = 0; i < count.Length; i++)
         {
             if (last1 != i && last2 != i && count[i] > 0)
             {
                 count[i]--;
                 sum += go(last2, i, count);
                 if (sum < 0)
                     throw new Exception();
                 count[i]++;
             }
         }
         {{komm|// Spara i cachen. Vi sparar värdet + 1 för att skilja från 0 som innebär ocachat.}}
         memo[last1, last2, hc] = sum+1;
         return sum;
     }
 }