Editing 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 &les; n &les; 100.000
* 1 &les; xi &les; 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 introduse corespund restricțiilor impuse.
: 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 ==
<syntaxhighlight lang="python" line>
def cmmdc(a, b):
    while b:
        r = a % b
        a = b
        b = r
    return a

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

def main():
    with open('cartonase1.in', 'r') as fin:
        n = int(fin.readline())
        nums = list(map(int, fin.readline().split()))
        if not validate_input(n, nums):
            print("Datele nu corespund restricțiilor impuse.")
            return
        
        x = nums[0]
        ok = True
        for i in range(2, n+1):
            y = nums[i-1]
            x = cmmdc(x, y)
            if x == 1:
                print(i)
                ok = False
                break
        if ok:
            print(-1)

if __name__ == '__main__':
    print("Datele sunt introduse corect.")
    main()


</syntaxhighlight>
== Explicație rezolvare ==
În funcția validate_input, se verifică dacă intrările corespund restricțiilor cerute de enunțul problemei. Dacă numărul de copii este în afara intervalului [2, 100000] sau numerele de cartonașe sunt în afara intervalului [1, 100000000], atunci se afișează un mesaj corespunzător și se returnează valoarea False. <br> Funcția cmmdc este o implementare simplă a algoritmului lui Euclid pentru calcularea celui mai mare divizor comun dintre două numere. Se utilizează în bucla for pentru a calcula cel mai mare divizor comun dintre numerele de cartonașe primite de jucători. <br> În funcția main, se citește numărul de copii și apoi se citește numărul de cartonașe al primului jucător. Apoi se parcurg numerele de cartonașe ale celorlalți jucători, calculând cel mai mare divizor comun dintre numărul de cartonașe al jucătorului curent și numărul de cartonașe pus pe masă de jucătorul anterior. Dacă la un moment dat cel mai mare divizor comun este 1, atunci se afișează numărul de ordine al jucătorului curent și se iese din bucla for. Dacă niciun jucător nu ajunge să pună pe masă un singur cartonaș, se afișează valoarea -1. <br> Funcția validate_input este apelată înainte de bucla for pentru a verifica dacă datele de intrare respectă restricțiile.