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

Funcția cmmdc calculează cel mai mare divizor comun între două numere folosind algoritmul lui Euclid.
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.