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 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.
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.
Î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.
Funcția validate_input este apelată înainte de bucla for pentru a verifica dacă datele de intrare respectă restricțiile.