3340 - Perfect 1

From Bitnami MediaWiki
Revision as of 19:33, 10 November 2023 by Ghisa Catalin (talk | contribs)

Cerinţa

Cerința Se dau n numere naturale. Să se determine cel mai mare număr perfect mai mic sau egal cu 8128 care poate fi scris ca produs al unora dintre numerele date. Un număr natural este perfect dacă dublul său este egal cu suma divizorilor săi.

Date de intrare

Fișierul de intrare perfect1in.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire perfect1out.txt va conține pe prima linie numărul S, reprezentând cel mai mare număr perfect care poate fi scris ca produs al unora dintre numerele de pe a doua linie a fișierului de intrare sau mesajul NU dacă nu se nu există un asemenea număr.

Restricţii şi precizări

  • 1 ⩽ n ⩽ 100
  • numerele de pe a doua linie a fișierului de intrare și numerele perfecte determinate vor fi mai mici decât 8128

Exemplu

perfect1in.txt
7
2 7 9 2 2 31 2
perfect1out.txt
Datele de intrare corespund restrictiilor impuse
496


Exemplu 2

perfect1in.txt
6
2 31 127 2 2 5
perfect1out.txt
Datele de intrare corespund restrictiilor impuse
NU


Exemplu 3

perfect1in.txt
7
2 7 9 2 2 ab 2
perfect1out.txt
Datele de intrare nu corespund restrictiilor impuse


Rezolvare

<syntaxhighlight lang="python" line>

def validare(numar, arr, fileout): # functia de validare a datelor de intrare

   if len(arr) != numar:
       raise ValueError
   if numar > 300000:
       raise ValueError
   for numar in arr:
       if not isinstance(numar, int) or numar < 1 or numar > 2147483647:
           raise ValueError
   fileout.write("Datele de intrare corespund restrictiilor impuse\n")


def perfect_numbers(numar_1, arr):

   perfects = [6, 28, 496, 8128]
   max_perfect = -1
   for i in range(1, 1 << numar_1):
       prod = 1
       for j in range(n):
           if (i >> j) & 1:
               prod *= arr[j]
       if prod in perfects and prod > max_perfect:
           max_perfect = prod
   return max_perfect


if __name__ == '__main__':

   file_in = open("perfect1in.txt", "r")         # declararea fisierelor
   file_out = open("perfect1out.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)
   try:
       n = int(file_in.readline())
       numbers = list(map(int, file_in.readline().split()))
       validare(n, numbers, file_out)                 # apelul functiei de validare
       result = perfect_numbers(n, numbers)               # apelul functiei de rezolvare
       if result != -1:
           file_out.write(str(result))  # Dacă am găsit un număr perfect, îl scriem în fișier
       else:
           file_out.write("NU")  # Dacă nu am găsit niciun număr perfect, scriem "NU" în fișier
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>


Explicatie

Inmultind 2*2*2*31*2 obținem numărul 496 .