== include(page="template/taskheader" task_id="robotei") ==
==Include(page="template/taskheader" task_id="robotei")==
Poveste ...
h2. Cerinta
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$,
h2. Restrictii
...
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
| robotei.in | robotei.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. robotei.in |_. robotei.out |
| 3 4 1 2 2 3 1 1
| 1 2
2 6
3 1 |
h3. Explicatii
== include(page="template/taskfooter" task_id="robotei") ==
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")==
