Fişierul intrare/ieşire:reg.in, reg.outSursăStelele Informaticii 2005, clasele 11-12
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.6 secLimită de memorie11264 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Reg

Algostorm a inceput sa programeze satelitii intergalactici intr-un limbaj de programare denumit SuperP++ . Un program in SuperP++ consta dintr-o serie de instructiuni (numele acestor instructiuni sunt niste numere intregi) care trebuiesc executate in ordine. Pentru a fi executata, o instructiune trebuie citita din registri (acestia sunt in numar de K si fiecare registru poate retine cel mult o instructiune la un moment dat). Daca o instructiune nu exista in registri, aceasta trebuie incarcata inainte de a fi executata. O instructiune poate fi incarcata intr-un registru gol sau intr-un registru folosit caz in care instructiunea curenta este stearsa din registru (pentru eliberarea acestuia). Odata stearsa, o instructiune nu mai poate fi incarcata in nici un registru si la intalnirea ei in executarea programului acesta se intrerupe.

Cerinta

Algostorm a scris un program compus din N instructiuni. Stiind numarul de registri, K, aflati care este numarul maxim de instructiuni din programul lui Algostorm care pot fi executate pana la intreruperea lui, respectand regulile de incarcare si citire.

Date de intrare

In fisierul reg.in se afla pe prima linie un numar T reprezentand numarul de teste care vor urma. Pe urmatoarele T linii se afla cate 5 numere: A, B, C, N, K. Programul lui Algostorm va fi descris de urmatoarele relatii (Xi fiind instructiunea cu numarul i, i = 1..N)

X1 = 1, Xi = (Xi-1 * A + B * i) mod C pentru i = 2..N

Date de iesire

Fisierul de iesire reg.out va contine T linii: pentru fiecare test se va afisa pe cate o linie numarul maxim de instructiuni din programul lui Algostorm care pot fi executate utilizand exact K registri.

Restrictii si precizari

  • 1 ≤ N ≤ 2 000 000
  • 1 ≤ T ≤ 10
  • 1 ≤ A, B, C, K ≤ 500 000
  • C este mereu prim
  • Suma numarului de instructiuni ale tuturor programelor dintr-un fisier de intrare nu va depasi 4 000 000
  • Pentru 70% din fisierele de intrare N ≤ 400 000
  • Instructiunile se vor executa in ordine, de la 1 catre N

Exemplu

reg.inreg.out
2
1 1 7 5 1
2 3 5 8 2
3
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content