Tävlingsprogrammering/Uppgifter/Spellistan

Spellistan

Du vill göra din egen musikspellista. Du börjar med att skaffa n låtar som du aldrig hört innan (numrerade från 1 till n). Sedan lyssnar du igenom låtarna och tar bort dem du inte tycker om. Nu har du en färdig spellista!

Du vill dock inte lyssna igenom låtarna sekventiellt, utan i slumpad ordning. Du bestämmer dig för följande deterministiska slumpalgoritm. Du börjar med ett tal x₀ och en modulator M och beräknar sedan fram resterande tal med följande formel:

x_n+1 = x_n² mod M

Du låter nu talet xi avgöra den i:te låten du ska lyssna på genom att starta från den första kvarvarande låten och trycka framåt xi gånger (efter den sista kommer du tillbaka till den första o.s.v.). Observera att det är x₁ som avgör vilken den första låten blir.

Antaget att du vet vilka m låtar du kommer ogilla i förväg, skriv ett program som tar reda på i vilken ordning dessa kommer tas bort från spellistan samt hur många låtar du hinner lyssna på tills spellistan är färdig. Indata

Indata består av tre rader. På första raden står de två heltalen x₀ och M, som beskriver slumpalgoritmen (0 ≤ x₀ < M ≤ 100000). På andra raden står de två heltalen n och m, antalet låtar totalt och antalet låtar som ska tas bort (0 ≤ m < n ≤ 100). På den tredje raden står m unika heltal mellan 1 och n, numren på de låtar som du inte gillar. Utdata

Utdatan ska bestå av 2 rader. Den första ska innehålla alla m låtnumrena i den ordning de togs bort, och den sista raden ska innehålla det totala antalet låtar du har lyssnat på när den sista låten tagits bort. I samtliga testfall kommer detta antal vara under 10000.

Exempel: Indata

3 19 
4 3
1 4 3

Exempel: Utdata

3 4 1
5

Exempel: Förklaring

Slumpalgoritmen ger talen 9, 5, 6, 17, 4, 16, 9... Vidare har vi 4 låtar varav vi ogillar 3. Notera att vi har hunnit lyssna på den omtyckta låten 2 gånger innan den sista dåliga låten elimineras och vi är klara (vi lyssnade på låtarna i ordningen 2, 2, 3, 4, 1).

Lösning

Här är det bara att simulera processen. Det finns dock två viktiga saker att tänka på. Dels kan det uppstå overflow om man gör operationen x_n*x_n med vanliga 32-bitars heltal, så man måste använda 64-bitars heltal (detta var lite olyckligt eftersom det inte fanns något exempel som visade detta). Dels kan programmet ta för lång tid om man verkligen simulerar att man trycker sig fram x_n gånger. Detta är dock lätt avhjälpt eftersom man kan hålla koll på hur många låtar K man har kvar, och då räcker det att trycka fram x_n mod K gånger.

Lösning i C:

#include <stdio.h>

int main() {
  int x0,M,n,m,i,j,k,tot,stat[100];      //stat[i]=0 för bra låtar, 1 för dåliga låtar som är kvar och 2 för dåliga låtar som är borttagna
  long long x;
  scanf("%d %d %d %d", &x0, &M, &n, &m);
  for(i=0;i<n;i++) stat[i]=0;   
  for(i=0;i<m;i++) {
    scanf("%d",&k);
    stat[k-1]=1;   
  }
  k=n;   //Håll reda på antal låtar kvar
  x=x0;
  tot=0;
  while(k>n-m) {     //Så länge vi inte tagit bort alla m dåliga
    x=(x*x)%M;      //Generera ett nytt slumptal
    i=j=0;    
    while(1) {       //Loopa fram tills vi hittat x%k låtar som inte är borttagna
      if(stat[i]<2) { 
        if(j==x%k) break;
        j++;
      }
      i++;
    }
    if(stat[i]==1) {   //Om den var dålig så ta bort den
      stat[i]=2;
      printf("%d ",i+1);
      k--;
    }
    tot++;    //Öka antalet lyssnade låtar
  }
  printf("\n%d\n",tot);
  return 0;
}