Editing 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 &les; n &les; 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

# 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

# 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()))

# 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)

# 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''' .