== include(page="template/taskheader" task_id="ruleta1") ==
Nicușor este elev în clasa a VI-a și s-a gândit că este suficient de mare ca să inventeze un joc nou. Are doar o foaie de hârtie și un pix. Scrie mai întâi n numere naturale în cerc. Acestea formează Ruleta numerelor. Jocul se desfășoară după următoarele reguli:
- se parcurge șirul numerelor în sensul deplasării acelor de ceasornic;
- se pornește de fiecare dată de la același element;
- se execută de fiecare dată o rotație completă;
- fiecare element nenul se scade din elementul imediat următor doar dacă este mai mic sau egal cu acesta și nenul;
Exemplu. Dacă notăm cu R1, R2, R3, R4, R5, R6, R7, R8 șirul numerelor ce formează ruleta din figura 1, atunci, o rotație completă realizează următoarele modificări asupra numerelor din listă:
_Notă: această problemă a fost modificată față de original:_
h2. Cerinta
* _Am înlocuit testele 5 și 6 cu teste maximale, inexistente în original._
* _Am mărit timpul de la o secundă, pentru a putea accepta soluții eficiente._
Scrieți un program care să determine, pentru un șir de n numere naturale care indică starea inițială a ruletei, numărul r de rotații complete efectuate respectând regulile jocului până la încheierea acestuia și numărul t al elementelor nenule aflate în șir la încheierea jocului.
_Soluția comisiei nu trece cele două teste maximale, deci cei ce implementați acea soluție veți pica testele maximale. Succes!_
Nicușor este elev în clasa a VI-a și s-a gândit că este suficient de mare ca să inventeze un joc nou. Are doar o foaie de hârtie și un pix. Scrie mai întâi *n* numere naturale în cerc. Acestea formează _[*Ruleta numerelor*]_. Jocul se desfășoară după următoarele reguli:
* se parcurge șirul numerelor în sensul deplasării acelor de ceasornic;
* se pornește de fiecare dată de la același element;
* se execută de fiecare dată o rotație completă;
* fiecare element nenul se scade din elementul imediat următor doar dacă este mai mic sau egal cu acesta și nenul;
h3. Exemplu
Dacă notăm cu [*R[~1~]*], [*R[~2~]*], [*R[~3~]*], [*R[~4~]*], [*R[~5~]*], [*R[~6~]*], [*R[~7~]*], [*R[~8~]*] șirul numerelor ce formează ruleta din figura 1, atunci, o rotație completă realizează următoarele modificări asupra numerelor din listă:
!problema/ruleta1?ruleta1_1.jpg! !problema/ruleta1?ruleta1_2.jpg!
* ruleta se oprește atunci când execută o rotație completă și nu se modifică nici o valoare din șirul elementelor.
h3. Exemplu
Pentru ruleta din figura 1 se execută 4 rotații (dintre care 3 în care se fac modificări):
!problema/ruleta1?ruleta1_3.jpg!
h2. Cerințe
Scrieți un program care să determine, pentru un șir de *n* numere naturale care indică starea inițială a ruletei, numărul *r* de rotații complete efectuate respectând regulile jocului până la încheierea acestuia și numărul *t* al elementelor nenule aflate în șir la încheierea jocului.
h2. Date de intrare
Fișierul de intrare $ruleta1.in$ conține pe prima linie numărul n de numere naturale așezate în cerc iar pe linia a doua, separate prin câte un spațiu, cele n valori , în ordinea deplasării, începând cu elementul de la care pornește ruleta.
Fișierul de intrare $ruleta1.in$ conține pe prima linie numărul *n* de numere naturale așezate în cerc iar pe linia a doua, separate prin câte un spațiu, cele *n* valori, în ordinea deplasării, începând cu elementul de la care pornește ruleta.
h2. Date de ieșire
Fișierul de ieșire $ruleta1.out$ conține pe prima linie, separate printr-un spațiu, valorile r și t (în această ordine).
Fișierul de ieșire $ruleta1.out$ conține pe prima linie, separate printr-un spațiu, valorile *r* și *t* (în această ordine).
h2. Restricții
* 2 ≤ n ≤ 10000
* Numerele de pe ruletă sunt numere naturale mai mici sau cel mult egale cu 30000 .
* 2 ≤ *n* ≤ 10 000
* Numerele de pe ruletă sunt numere naturale mai mici sau cel mult egale cu 30 000 .
* Pentru aflarea corectă a numărului *r* de rotații se acordă 70% din punctajul pe test; punctajul integral se acordă dacă ambele valori afișate sunt corecte.
h2. Exemplu
table(example).
table(example).
|_. ruleta1.in |_. ruleta1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8
1 2 3 4 3 2 3 1
| 4 3
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="ruleta1") ==
