3340 - Perfect 1

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 perfect1.in 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 perfect1.out 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

perfect1.in

7

2 7 9 2 2 31 2

perfect1.out

496

Exemplu 2

perfect1.in

6

2 31 127 2 2 5

perfect1.out

NU

Rezolvare

<syntaxhighlight lang="python" line> def div_sum(n):

   sum = 1
   i = 2
   while i * i <= n:
       if n % i == 0:
           if i * i != n:
               sum = sum + i + n/i
           else:
               sum = sum + i
       i += 1
   return sum

1. Funcția perfect_numbers generează toate submulțimile de numere din arr și verifică dacă produsul lor este un număr perfect

def perfect_numbers(n, arr):

   perfects = [6, 28, 496, 8128]  # Lista numerelor perfecte mai mici sau egale cu 8128
   max_perfect = -1  # Inițializăm cel mai mare număr perfect găsit ca fiind -1 (adică nu am găsit niciunul încă)
   for i in range(1, 1 << n):  # Generăm toate submulțimile de numere din arr
       prod = 1
       for j in range(n):
           if (i >> j) & 1:  # Verificăm dacă bitul j din reprezentarea binară a lui i este setat (adică dacă numărul j este în submulțime)
               prod *= arr[j]  # Dacă este, îl înmulțim cu produsul curent
       if prod in perfects and prod > max_perfect:  # Dacă produsul este un număr perfect și este mai mare decât cel mai mare număr perfect găsit până acum, îl actualizăm
           max_perfect = prod
   return max_perfect

1. Citim datele de intrare din fișierul perfect1.in

with open('perfect1.in', 'r') as fin:

   n = int(fin.readline())
   arr = list(map(int, fin.readline().split()))

1. Calculăm cel mai mare număr perfect care poate fi obținut ca produs al unora dintre numerele date

result = perfect_numbers(n, arr)

1. Scriem rezultatul în fișierul perfect1.out

with open('perfect1.out', 'w') as fout:

   if result != -1:
       fout.write(str(result))  # Dacă am găsit un număr perfect, îl scriem în fișier
   else:
       fout.write("NU")  # Dacă nu am găsit niciun număr perfect, scriem "NU" în fișier

</syntaxhighlight>

Explicatie

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