2176 - Ruleta

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ă:

- 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ța

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 ruleta.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 ruleta.out conţine pe prima linie, separate printr-un spaţiu, valorile r şi t (în această ordine).

Restricții și precizări

• 2 ≤ n ≤ 10000;
• numerele de pe ruletă sunt numere naturale mai mici sau cel mult egale cu 30000;

Exemplu:

ruleta.in

8
1 2 3 4 3 2 3 1

ruleta.out

4 3

def roulette_game(numbers):
    n = len(numbers)
    rotations = 0
    modified = True

    while modified:
        modified = False
        rotations += 1
        new_numbers = numbers[:]
        for i in range(n):
            if numbers[i] != 0 and numbers[i] <= numbers[(i + 1) % n]:
                new_numbers[(i + 1) % n] -= numbers[i]
                modified = True
        numbers = new_numbers

    non_zero_count = sum(1 for x in numbers if x != 0)
    return rotations, non_zero_count

# Exemplu de utilizare
initial_numbers = [3, 4, 5, 6, 7, 8, 9, 10]
rotations, non_zero_count = roulette_game(initial_numbers)
print(f"Numărul de rotații: {rotations}")
print(f"Numărul de elemente nenule rămase: {non_zero_count}")