Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | reg.in, reg.out | Sursă | Stelele Informaticii 2005, clasele 11-12 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de | |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 11264 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Reg
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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
. In timpul concursului s-a impus o limita de memorie de 7MB pentru segmentul de date si 1MB pentru stiva.
Exemplu
| reg.in | reg.out |
| 2 | 3 |
| 1 1 7 5 1 | 6 |
| 2 3 5 8 2 | |
