Reg

reg

==Include(page="template/taskheader" task_id="reg")==

== include(page="template/taskheader" task_id="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.

Poveste ...

h2. 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.
 
h2. 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 ({$X{~i~}$} fiind instructiunea cu numarul $i$, {$i = 1..N$})

h2. Restrictii

$X{~1~} = 1$, $X{~i~} = (X{~i-1~} * A + B * i)$ mod $C$ pentru $i = 2..N$

...

h2. Date de iesire

h2. Date de intrare

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.

...

h2. Restrictii si precizari

h2. Date de iesire

* $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$

...

h2. Exemplu

table(example). |_. reg.in |_. reg.out |
| 2
1 1 7 5 1
2 3 5 8 2
| 3
6 |

| reg.in | reg.out |
| linia1
linia2
linia3
| linia1
linia2
|

==Include(page="template/taskfooter" task_id="reg")==
 
 

== include(page="template/taskfooter" task_id="reg") ==

712