Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | robotei.in, robotei.out | Sursă | preONI 2006 Runda Finala |
| Autor | Silviu-Ionut Ganceanu | Adăugată de | |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Robotei
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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:
newXi = (oldXi2 + offsetX) modulo modX
newYi = (oldYi2 + offsetY) modulo modY,
unde (oldXi, oldYi) reprezinta pozitia veche a robotelului i (modul de numerotare al roboteilor nu este important) si (newXi, newYi) noua lui pozitie; offsetX, offsetY, modX si modY sunt comune regulilor de miscare ale roboteilor.
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.
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.
Date de iesire
Fisierul de iesire va contine cate o linie pentru fiecare n cate doi intregi, n si Cn cu semnificatia: "Cn 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 Cn este diferit de 0.
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.
| 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 |
Exemplu
| robotei.in | robotei.out | Explicatii |
| 3 4 1 2 2 3 1 1 | 1 2 | Sunt 3 × 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 | ||
