Tävlingsprogrammering/Uppgifter/Kulram

Se problemet

Den här uppgiften kan lösas på två olika sätt. Antingen genomför man helt enkelt den beskrivna proceduren N gånger, eller så översätter man ställningen till ett tal, adderar N och översätter tillbaka det nya talet till en ställning.

Om N är ett stort tal går den andra metoden naturligtvis mycket snabbare. Därför var indata valt så att den första metoden endast gav 3 av 5 poäng. Intressant nog är datorerna nu så snabba att den första metoden går på någon sekund även om N är 1 miljard, därför var vi tyvärr tvungna att låta N vara ett mycket stort tal i de sista testfallen, vilket gav en extra komplikation i vissa språk eftersom 64-bitars heltal behövde användas.

Metod 1, brute force

Lösningsförslag i C:

#include <stdio.h>

int main() {
  int v[20],h[20];
  int i,j,k,R,N;
  scanf("%d",&R);
  for(i=R-1;i>=0;i--) scanf("%d %d",&v[i],&h[i]);
  scanf("%d",&N); 
  for(;N>0;N--) {   //Loopa N gånger
    for(i=0;i<R;i++) if(h[i]>0) break;   //Hitta första raden med antalet högerkulor > 0
    if(i<R) {   //Om det fanns en sådan "F-rad", flytta en kula till vänster.
      h[i]--;
      v[i]++;
    }
    for(j=0;j<i;j++) {   //Flytta alla kulor nedanför F-raden till höger.
      h[j]+=v[j];
      v[j]=0;
    }
  }
  for(i=R-1;i>=0;i--) {  //Skriv ut den nya ställningen
    printf("%d %d\n",v[i],h[i]);
  }  
  return 0;
}

Metod 2, omvandling till tal

Om det vore samma antal kulor K på varje rad så skulle det helt enkelt handla om en omvandling från basen K+1 till ett vanligt heltal (M) och sedan en omvandling av det nya talet (M+N) tillbaka till basen K+1. Detta exemplifieras i uppgiftens första figur där det är 9 kulor och därmed siffrorna kan läsas i vår vanliga bas 10.

Man kan tänka ungefär likadant när antalet kulor varierar. Istället för att ha en konstant bas för alla siffror i talet har vi nu flera baser b₁, b₂, ... b_R, en för varje position i talet. Den första siffran från höger, entalssiffran, är ju alltid värd 1, men den andra siffran är värd b₁, den tredje är värd b₁*b₂, den fjärde är värd b₁*b₂*b₃ o.s.v., givetvis multiplicerat med själva siffran. Jämför med vårt vanliga system med konstant bas, då är siffrorna värda 1, 10, 100 o.s.v.

Att omvandla tillbaka till den varierade basen kan verka lite klurigare, men från resonemanget ovan ser vi ju att alla bidragen utom entalsbidraget är delbara med b₁, så entalssiffran ges helt enkelt av talet MOD b₁, där MOD är resten i heltalsdivision (jfr. entalssiffran i decimaltalet 134 är 4 eftersom 134 MOD 10 = 4). På samma sätt är ju alla bidragen utom de två första delbara med b₁*b₂, så nästa siffra kan fås genom att först "ta bort" entalssiffran genom att dividera med b₁, och sedan ta det kvarvarande talet MOD b₂ (jfr. tiotalssiffran i 134 ges av 13 MOD 10 = 3).

Att hantera "overflow" då kulramen slår om till 0 kan naturligtvis enkelt göras genom att låta det nya talet vara (M+N) MOD B, där B=b₁*b₂*b₃*....b_R, men faktum är att det inte behövs, för ovanstående algoritm kommer inte påverkas av bidrag som är delbara med B.

Ett bra trick när man hanterar 64-bitarstal ("long long" i C/C++) är att låta alla tal som opererar med de stora talen också ha datatypen long long, så att inte operationen blir en 32-bitarsoperation.

Lösningsförslag i C:

#include <stdio.h>

long long todec(int R, long long v[], long long b[]) {  //Från ställning till tal
  int i;
  long long d,k;
  d=0;
  k=1;    //Första siffran, "entalssiffran" är alltid värd 1.
  for(i=0;i<R;i++) {
    d+=k*v[i];   //Siffrans bidrag till talet
    k*=b[i];    //Hur mycket ska nästa siffra i talet vara värd? 
  }
  return d;
}

void tokul(int R, long long d, long long v[], long long b[]) {  //Från tal till ställning
  int i;
  for(i=0;i<R;i++) {
    v[i]=d % b[i];    //Räkna ut siffran genom att ta talet MOD basen
    d/=b[i];    //Dividera talet med basen för att få talets värde "utan sista siffran".
  }
}

int main() {
  long long v[20],h[20],b[20];   
  int i,j,k,R;
  long long M,N;
  scanf("%d",&R);
  for(i=R-1;i>=0;i--) {
    scanf("%lld %lld",&v[i],&h[i]);
    b[i]=v[i]+h[i]+1;   //Basen = antalet kulor + 1
  }
  scanf("%lld",&N); 
  M=todec(R,v,b);    //Omvandla ställningen till ett tal
  tokul(R,M+N,v,b);   //Omvandla det nya talet tillbaka till en ställning
  for(i=R-1;i>=0;i--) {  //Skriv ut den nya ställningen
    printf("%lld %lld\n",v[i],b[i]-v[i]-1);
  }  
  return 0;
}