==Include(page="template/taskheader" task_id="robotei")==
==Include(page="template/raw")==
Robotei
In fiecare celula a unui caroiaj de dimensiuni NxN se afla plasat cate un robotel. Coltul din stanga sus al caroiajului are coordonatele (0, 0) iar cel din dreapta jos (N-1, N-1). Roboteii sunt programati sa se miste, in fiecare secunda, dupa urmatoarea regula:
newX[i] = (oldX[i]^2 + offsetX) modulo modX
newY[i] = (oldY[i]^2 + offsetY) modulo modY,
unde (oldX[i], oldY[i]) reprezinta pozitia veche a robotelului i (modul de numerotare al roboteilor nu este important) si (newX[i], newY[i]) noua lui pozitie; offsetX, offsetY, modX si modY sunt comune regulilor de miscare ale roboteilor.
h2. Cerinta
Stiind ca fiecare robotel va efectua M mutari, aflati cati roboti trec prin pozitia (X, Y) de n ori, pentru fiecare n intre 0 si M.
h2. Date de Intrare
Prima linie a fisierului de intrare va contine 6 numere intregi separate de spatii: N, M, X, Y, modX, modY, offsetX si respectiv offsetY cu semnificatiile din enunt.
h2. Date de Iesire
Fisierul de iesire va contine cate o linie pentru fiecare n cate doi intregi, n si C[n] cu semnificatia: "C[n] robotei trec prin pozitia (X, Y) de exact n ori". Perechile de numere vor fi afisate in ordine crescatoare dupa n si vor fi afisate doar cele pentru care C[n] este diferit de 0.
h2. Restrictii si precizari
o Toate numerele din fisierul de intrare sunt intregi din intervalul [0, 1.000.000]
o Aceasta problema va fi testata cu 10 de teste, fiecare valorand cate 10 puncte. Valorile utilizate in teste pentru N, M, modX si modY se regasesc in tabelul de mai jos.
o Pe parcurs, o celula poate contine mai multi robotei.
| Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| N | 20 | 33 | 61 | 43139 | 83 | 504 | 32668 | 906 | 1523 | 44339 |
| M | 1000 | 2100 | 400745 | 337654 | 237891 | 367398 | 500000 | 325000 | 476388 | 666732 |
| modX | 13 | 31 | 40 | 54 | 72 | 270 | 561 | 877 | 997 | 997 |
| modY | 19 | 29 | 50 | 65 | 69 | 256 | 437 | 809 | 991 | 1000 |
h2. Exemplu
|robotei.in |robotei.out|Explicatii |
|3 4 1 2 2 3 1 1|1 2 |Sunt 3 x 3 = 9 robotei. Robotelul situat in celula (3|
| | |2) va avea urmatorul parcurs: (3 2) -> (0 2) -> (1 2)|
| |2 6 |-> (0 2) -> (1 2). In consecinta, el trece de 2 ori|
| | |prin pozitia (1 2). |
| |3 1 | |
==Include(page="template/taskheader" task_id="robotei")==
In fiecare celula a unui caroiaj de dimensiuni $NxN$ se afla plasat cate un robotel. Coltul din stanga sus al caroiajului are coordonatele ({$0$}, {$0$}) iar cel din dreapta jos ({$N-1$}, {$N-1$}). Roboteii sunt programati sa se miste, in fiecare secunda, dupa urmatoarea regula:
p=. $newX{~i~} = (oldX{~i~}^2^ + offsetX) modulo modX$
p=. $newY{~i~} = (oldY{~i~}^2^ + offsetY) modulo modY$,
unde ({$oldX{~i~}, oldY{~i~}$}) reprezinta pozitia veche a robotelului $i$ (modul de numerotare al roboteilor nu este important) si ({$newX{~i~}, newY{~i~}$}) noua lui pozitie. $offsetX$, $offsetY$, $modX$ si $modY$ sunt comune regulilor de miscare ale roboteilor.
h2. Cerinta
Stiind ca fiecare robotel va efectua $M$ mutari, aflati cati roboti trec prin pozitia ({$X$}, {$Y$}) de $n$ ori, pentru fiecare $n$ intre $0$ si $M$.
h2. Date de intrare
Prima linie a fisierului de intrare va contine $8$ numere intregi separate de spatii: $N$, $M$, $X$, $Y$, $modX$, $modY$, $offsetX$ si respectiv $offsetY$ cu semnificatiile din enunt.
h2. Date de iesire
Fisierul de iesire va contine cate o linie pentru fiecare $n$ cate doi intregi, $n$ si $C{~n~}$ cu semnificatia: "$C{~n~}$ robotei trec prin pozitia ({$X$}, {$Y$}) de exact $n$ ori". Perechile de numere vor fi afisate in ordine crescatoare dupa $n$ si vor fi afisate doar cele pentru care $C{~n~}$ este diferit de $0$.
h2. Restrictii si precizari
* Toate numerele din fisierul de intrare sunt intregi din intervalul $[0, 1.000.000]$
* Aceasta problema va fi testata cu $10$ de teste, fiecare valorand cate $10$ puncte. Valorile utilizate in teste pentru $N$, $M$, $modX$ si $modY$ se regasesc in tabelul de mai jos.
* Pe parcurs, o celula poate contine mai multi robotei.
table(numbers). |_. Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|_. N | 20 | 33 | 61 | 43139 | 83 | 504 | 32668 | 906 | 1523 | 44339 |
|_. M | 1000 | 2100 | 400745 | 337654 | 237891 | 367398 | 500000 | 325000 | 476388 | 666732 |
|_. modX | 13 | 31 | 40 | 54 | 72 | 270 | 561 | 877 | 997 | 997 |
|_. modY | 19 | 29 | 50 | 65 | 69 | 256 | 437 | 809 | 991 | 1000 |
h2. Exemplu
table(example). |_. robotei.in |_. robotei.out |
| 3 4 1 2 2 3 1 1
| 1 2
2 6
3 1 |
h3. Explicatii
Sunt 3 x 3 = 9 robotei. Robotelul situat in celula (3 2) va avea urmatorul parcurs: (3 2) -> (0 2) -> ({%{color:red}1 2%}) -> (0 2) -> ({%{color:red}1 2%}). In consecinta, el trece de 2 ori prin pozitia ({%{color:red}1 2%}).
==Include(page="template/taskfooter" task_id="robotei")==
==Include(page="template/taskfooter" task_id="robotei")==
