2881 - Cartonase 1

Cerinţa

Într-o zi, câțiva copii plictisiți de “Popa Prostul”, au inventat jocul “Popa Prostul 2”. Acest joc se joacă cu mai multe cartonașe identice. La început, fiecare jucător primește un număr de cartonașe. Primul jucător pune pe masă un număr de cartonașe egal cu cel mai mare divizor al numărului de cartonașe pe care îl avea în mână. Următorul pune un număr maxim de cartonașe, divizor al numărului de cartonașe pe care le are în mână, dar și divizor al numărului de cartonașe pus de jucătorul dinainte. Jocul continuă până când unul dintre copii pune jos un singur cartonaș. Jucătorul care va fi nevoit să pună un singur cartonaș va fi pierzătorul.

Dându-se numărul n de copii și numărul de cartonașe pe care îl primește fiecare, să se determine numărul de ordine al copilului care va pierde jocul.

Date de intrare

Pe prima linie a fișierului de intrare cartonase1.in se va găsi numărul n de copii. Pe a doua linie vor fi n numere: x1,x2…xn reprezentând numărul de cartonașe pe care îl primește fiecare jucător.

Date de ieşire

Dacă datele sunt introduse corect, în fișier se va afișa: "Datele sunt introduse corect.", apoi pe prima linie a fișierului cartonase1.out se va scrie numărul de ordine al pierzătorului sau valoarea -1 dacă nu există pierzător.În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 2 ⩽ n ⩽ 100.000
• 1 ⩽ xi ⩽ 100.000.000
• Primul jucător va avea numărul de ordine 1.

Exemplu

cartonase1.in

8

30 15 6 18 303 45 44 25

cartonase1.out

Datele sunt introduse corect.

7

Explicație

Primul jucător va pune 30 de cartonaşe. Al doilea jucător va pune 15 cartonaşe. Al treilea jucător va pune 3 cartonaşe. Jucătorii 4, 5 şi 6 vor pune 3 cartonaşe fiecare. Jucătorul cu numărul 7 va fi obligat să pună 1 cartonaş şi va pierde jocul.

Rezolvare

def cmmdc(a, b):
    while b:
        r = a % b
        a = b
        b = r
    return a

def validare_date(n, xi):
    if not (2 <= n <= 100_000):
        return False
    for num in xi:
        if not (1 <= num <= 100_000_000):
            return False
    return True

if __name__ == '__main__':
    with open('cartonase1.in', 'r') as fin, open('cartonase1.out', 'w', encoding='utf-8') as fout:
        n = int(fin.readline())
        xi = list(map(int, fin.readline().split()))
        if not validare_date(n, xi):
            fout.write("Datele nu corespund restricțiilor impuse.")
        else:
            fout.write("Datele sunt introduse corect\n")
            x = xi[0]
            ok = True
            for i in range(2, n + 1):
                y = xi[i - 1]
                x = cmmdc(x, y)
                if x == 1:
                    fout.write(str(i))
                    ok = False
                    break
            if ok:
                fout.write("-1")

Explicație rezolvare

Funcția cmmdc calculează cel mai mare divizor comun între două numere folosind algoritmul lui Euclid(algoritmul împarte deîmpărțitul la rest până când împărțitorul este 0, apoi returnează deîmpărțitul).
Funcția validate_date primește numărul de elemente n și o listă de numere xi și verifică dacă acestea respectă condițiile din enunț. Mai precis, n trebuie să fie între 2 și 100.000, iar fiecare element din xi trebuie să fie între 1 și 100.000.000.
În funcția principală, se deschide fișierul de intrare cartonase1.in în modul citire și fișierul de ieșire cartonase1.out în modul scriere, cu codificarea utf-8.
Se citește n și lista xi din fișierul de intrare.
Se validează datele citite din fișierul de intrare folosind funcția validate_date. Dacă acestea nu respectă condițiile din enunț, se afișează un mesaj de eroare în fișierul de ieșire și programul se termină. Altfel, se afișează un mesaj de confirmare în fișierul de ieșire.
Se inițializează variabila x cu primul element din xi.
Se parcurge lista xi de la al doilea element până la ultimul folosind o buclă for. Pentru fiecare element y, se calculează CMMDC-ul dintre x și y folosind funcția cmmdc și se actualizează valoarea lui x. Dacă x devine egal cu 1, se afișează poziția i în fișierul de ieșire și se setează variabila ok pe False. Se folosește variabila ok pentru a verifica dacă s-a găsit sau nu o pereche de numere cu CMMDC-ul egal cu 1. Dacă ok este True la finalul buclei, se afișează -1 în fișierul de ieșire.