1214 - Inventie

Sursa: [1]

---

Cerinţa

Lui Mihai îi place matematica distractivă, sau poate mai mult distracția decât matematica. Pentru a scăpa de teme, el a inventat operația ”smile” notată cu semnul ☺, operație care se aplică numerelor naturale nenule conform exemplelor de mai jos:

6☺4=210
9☺2=711
8☺5=313
7☺6=113
6☺6=12
6☺10=416
43☺1500=14571543
23☺23=46
Profesorul de matematică i-a promis nota 10 pentru invenție, numai dacă știe să determine corect numărul divizorilor pari pentru rezultatul obținut prin operația ”smile”. Astfel, Mihai a primit N perechi de numere (a,b) pentru care trebuie să calculeze a☺b și să determine dacă rezultatul obținut are divizori pari.
Scrieți un program care citește un număr natural N și N perechi de numere naturale (a,b) și afișează:

a) pentru fiecare pereche de numere (a,b), rezultatul a☺b; b) cel mai mic și cel mai mare rezultat a☺b care nu are divizori pari.

Date de intrare

Fişierul de intrare inventie.in conţine pe prima linie un număr natural N. Fiecare din următoarele N linii conține câte două numere naturale a b despărțite printr-un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi în fişierul de ieşire inventie.out:

• pentru fiecare din cele N perechi (a,b), se va afișa rezultatul a☺b, fiecare rezultat pe câte o linie, în ordinea în care perechile apar în fișierul de intrare;
• dacă toate cele N rezultate obținute au divizori pari, pe linia N+1 se va afișa valoarea 0 (zero);
• dacă s-a obținut măcar un rezultat fără divizori pari, atunci, pe linia N+1 se va afișa cel mai mic rezultat a☺b care nu are divizori pari, și pe linia N+2 se va afișa cel mai mare rezultat a☺b care nu are divizori pari. Dacă un singur rezultat nu are divizori pari, atunci acesta va fi scris și pe linia N+1 și pe linia N+2.

În caz contrar, pe ecran se va afișa: "Datele nu au fost introduse corect."

Restricţii şi precizări

• 1 ≤ N ≤ 20.
• a și b sunt numere naturale nenule de maxim 18 cifre fiecare

Exemple

Exemplul 1

inventie.in

8

6 4

9 2

8 5

7 6

6 6

6 10

43 1500

23 23

Ecran

Datele sunt introduse corect.

inventie.out

210

711

313

113

12

416

14571543

46

113

14571543

Exemplul 2

inventie.in

2

13 13

268 1244

Ecran

Datele sunt introduse corect.

inventie.out

26

9761512

0

Rezolvare

<syntaxhighlight lang="python" line>

1. 1214

def verificare_date(n: int, lista: list) -> bool:

   if not (1 <= n <= 20):
       return False
   for pereche in lista:
       if not (1 <= pereche[0] <= 10**18 and 1 <= pereche[1] <= 10**18):
           return False
   return True

def divizori_pari(nr: int) -> bool:

   divizori = 0
   for div in range(1, nr+1):
       if nr % div == 0 and div % 2 == 0:
           divizori += 1
   return divizori > 0

def smile(a: int, b: int) -> int:

   rez = 1
   for i in range(1, b+1):
       rez = rez * (a+i-1) // i
   return rez

if __name__ == '__main__':

   try:
       with open('inventie.in', 'r') as f:
           n = int(f.readline().strip())
           lista = []
           for i in range(n):
               a, b = map(int, f.readline().split())
               lista.append((a, b))
   except:
       print("Datele nu au fost introduse corect.")
       exit()

   if not verificare_date(n, lista):
       print("Datele nu au fost introduse corect.")
       exit()

   rezultate = []
   are_divizori_pari = True
   for pereche in lista:
       r = smile(pereche[0], pereche[1])
       rezultate.append(r)
       if divizori_pari(r):
           continue
       are_divizori_pari = False
       if 'min_fara_div_pari' not in locals():
           min_fara_div_pari = r
           max_fara_div_pari = r
       else:
           min_fara_div_pari = min(min_fara_div_pari, r)
           max_fara_div_pari = max(max_fara_div_pari, r)

   with open('inventie.out', 'w') as f:
       for r in rezultate:
           f.write(str(r) + '\n')
       if are_divizori_pari:
           f.write('0\n')
       else:
           f.write(str(min_fara_div_pari) + '\n')
           f.write(str(max_fara_div_pari) + '\n')
   print("Datele sunt introduse corect.")

</syntaxhighlight>

Explicație rezolvare

Funcția verificare_date(n: int, lista: list) -> bool primește doi parametri: n și lista. Verifică dacă n este între 1 și 20 și dacă toate elementele din lista sunt perechi de numere între 1 și 10^18. Dacă aceste condiții nu sunt îndeplinite, funcția returnează False. Dacă datele sunt valide, funcția returnează True.

Funcția divizori_pari(nr: int) -> bool primește un parametru nr și returnează True dacă nr are cel puțin un divizor par și False în caz contrar. Funcția parcurge toate numerele între 1 și nr și numără câți dintre aceștia sunt divizori ai lui nr și sunt numere pare. Dacă se găsește cel puțin un astfel de număr, funcția returnează True.

Funcția smile(a: int, b: int) -> int primește doi parametri a și b și returnează coeficientul binomial a+b-1 ales din b. Aceasta este o funcție matematică ce calculează combinațiile posibile ale a+b-1 elemente luate câte b.

În blocul de cod principal, se încearcă citirea datelor din fișierul "inventie.in". Dacă datele nu sunt valide, se afișează un mesaj de eroare și programul se încheie. Dacă datele sunt valide conform funcției verificare_date, se parcurge lista de perechi de numere și se calculează coeficienții binomiali folosind funcția smile. Rezultatele sunt stocate într-o listă rezultate. Se verifică apoi dacă toate valorile din listă au divizori pari folosind funcția divizori_pari. Dacă da, se afișează 0. În caz contrar, se găsesc minimul și maximul valorilor din listă care nu au divizori pari și se afișează acestea în fișierul "inventie.out". La final, se afișează un mesaj de confirmare că datele au fost introduse corect.