Fișierul intrare/ieșire	ruleta1.in, ruleta1.out	Sursă	OJI 2009 clasa a 6-a
Autor	Cristina Sichim	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	2 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ruleta1 ( clasa a 6-a )

Notă: această problemă a fost modificată față de original:

• 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.

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;

Exemplu

Dacă notăm cu R₁, R₂, R₃, R₄, R₅, R₆, R₇, R₈ șirul numerelor ce formează ruleta din figura 1, atunci, o rotație completă realizează următoarele modificări asupra numerelor din listă:

• ruleta se oprește atunci când execută o rotație completă și nu se modifică nici o valoare din șirul elementelor.

Exemplu

Pentru ruleta din figura 1 se execută 4 rotații (dintre care 3 în care se fac modificări):

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.

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.

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).

Restricții

• 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.

Exemplu