1773 - Happy

Sursa: [1]

Cerinţa

Lui Ionci ii place foarte mult matematica si informatica, asa ca s-a gandit sa creeze o operatie. Aceasta a numit-o "Happy", notata cu semnul ☺. Operatia se aplica doar numerelor naturale si dau ca rezultat tot un numar natural, conform exemplelor de mai jos:

2010 ☺ 2005 = 5 78 ☺ 54 = 6 999 ☺ 543 = 3 4 ☺ 9 = 1 5 ☺ 6 = 1 32 ☺ 24 = 8 10 ☺ 2 = 2

Profesorul de matematica, Vasy, i-a promis nota 10 pe invenție dacă pentru mai multe perechi de numere naturale veți determina cel mai mic număr rezultat cu număr par de divizori al operației Happy aplicată perechilor date și cel mai mare număr rezultat al operației Happy cu număr impar de divizori.

Date de intrare

Programul citește un număr natural N și N perechi de numere naturale a b.

Date de ieșire

Programul va afișa cel mai mic și cel mai mare rezultat obținut prin operația de mai sus, cu număr par, respectiv impar de divizori, separate printr-un spațiu.

Dacă datele sunt introduse corect, programul va rula.

Î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

1 ≤ N ≤ 20 cele 2 * N numere citite vor fi nenule și mai mici decât 1.000.000.

Exemplul 1

Intrare

2

87 87

1 1

Ieșire

87 1

Rezolvare

<syntaxhighlight lang="python" line>

1. 1773

import math

def validate_input(N, numbers):

   if N < 1 or N > 20 or len(numbers) != 2 * N:
       return False
   for num in numbers:
       if not (0 < num < 1000000):
           return False
   return True

if __name__ == '__main__':

   # read input values
   N = int(input())
   numbers = list(map(int, input().split()))

   # validate input values
   if not validate_input(N, numbers):
       print("Input values do not meet the requirements.")
   else:
       # functie care determina numarul de divizori al unui numar
       def numar_divizori(n):
           divizori = set()
           for i in range(1, int(math.sqrt(n))+1):
               if n % i == 0:
                   divizori.add(i)
                   divizori.add(n//i)
           return len(divizori)

       # functie care aplica operatia "Happy" pe o pereche de numere
       def happy(a, b):
           while a != b:
               if a > b:
                   a = a - b
               else:
                   b = b - a
           return a

       # setul de perechi de numere
       perechi = []
       for i in range(0, len(numbers), 2):
           perechi.append((numbers[i], numbers[i+1]))

       # initializam variabilele pentru cel mai mic si cel mai mare numar
       min_par = float('inf')
       max_impar = float('-inf')

       # iteram prin setul de perechi de numere
       for a, b in perechi:
           result = happy(a, b)
           divizori = numar_divizori(result)
           if divizori % 2 == 0 and result < min_par:
               min_par = result
           elif divizori % 2 == 1 and result > max_impar:
               max_impar = result

       # afisam rezultatele
       if min_par == float('inf'):
           print("NU EXISTA")
       else:
           print(f"Cel mai mic numar cu numar par de divizori: {min_par}")
       if max_impar == float('-inf'):
           print("NU EXISTA")
       else:
           print(f"Cel mai mare numar cu numar impar de divizori: {max_impar}")

</syntaxhighlight>

Explicatie cod:

Acest cod începe prin a importa biblioteca math, care va fi utilizată în mai multe funcții din program.

Funcția validate_input primește două argumente: N și numbers. Dacă N nu se află între 1 și 20 sau lungimea listei numbers nu este de două ori N, funcția returnează False. De asemenea, dacă orice număr din listă nu se află între 0 și 1000000, funcția va returna False. În caz contrar, funcția va returna True.

Următoarea secțiune verifică dacă programul este rulat ca un script (adică nu este importat în alt script). Dacă este, programul va citi două valori de la tastatură: N și numbers. N reprezintă numărul de perechi de numere pe care trebuie să le lucreze programul, iar numbers este lista de numere în sine.

Dacă input-ul nu este valid, se va afișa mesajul "Input values do not meet the requirements." În caz contrar, se va continua cu operațiile principale.

Următoarea funcție, numar_divizori, primește un număr n și returnează numărul de divizori ai acelui număr. Funcția utilizează un set pentru a ține evidența divizorilor și iterază prin numerele între 1 și radicalul pătrat din numărul n (deoarece divizorii între radicalul pătrat și numărul n pot fi obținuți prin împărțirea la divizorii din intervalul 1-radicalul pătrat și, de asemenea, divizorii între 1 și radicalul pătrat sunt perechi, deci doar unul dintre ei trebuie adăugat în set). Dacă n este divizibil cu i, atunci i și n/i sunt adăugați la set. Funcția returnează numărul de elemente din set, care reprezintă numărul de divizori.

Următoarea funcție, happy, primește două numere, a și b, și aplică operația "Happy" pe ele. Operația "Happy" este definită astfel: dacă a > b, a este înlocuit cu a - b, în caz contrar b este înlocuit cu b - a. Aceasta se repetă până când a = b, moment în care funcția returnează a.

Programul continuă prin a crea o listă de perechi de numere (numită perechi) din lista numbers.

Ulterior, sunt inițializate două variabile, min_par și max_impar, cu valorile inf și -inf, respectiv. Acestea vor fi utilizate pentru a găsi cel mai mic număr cu număr par de divizori și cel mai mare număr cu număr impar de divizori.