Editing 2037 - Grea

== Enunț ==
Vrăjitorul Arpsod are foarte multă treabă, așa că s-a gândit să vă ocupe timpul cu o problemă foarte grea, astfel încât acesta să poată lucra liniștit la proiectele sale despre stăpânirea lumii.

Acesta vă dă '''T''' numere naturale. Pentru fiecare număr '''A''' trebuie să găsiți cel mai mare '''K''' cu proprietatea că există un șir '''B''' de numere naturale nenule, nu neapărat distincte, astfel încât: '''(B1 + 1)(B2 + 1)...(BK + 1) = A'''
== Cerinţa ==
Arătați-i vrăjitorului că problema nu e suficient de grea pentru voi, găsind numărul K cerut într-un timp cât mai scurt, pentru fiecare din cele '''T''' numere.
== Date de intrare ==
Fișierul '''grea.in''' va conţine pe prima linie numărul natural '''T''', reprezentând numărul de valori date. Urmează apoi '''T''' linii. Pe fiecare linie va exista un număr '''A''', numărul dat de Arpsod.
== Date de ieșire == 

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează cel mai mare K cu proprietatea că există un șir B de numere naturale nenule, nu neapărat distincte, astfel încât: (B1 + 1)(B2 + 1)...(BK + 1) = A.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

== Restricţii şi precizări ==
* 1 &les; T &les; 500
* 2 &les; A &les; 2.000.000.000

== Exemple ==
; grea.in
: 1
: 4
; grea.out
: Datele sunt introduse corect.
: 2
== Explicație ==
Ne interesează rezultatul pentru un număr '''(4)'''
Şirul are '''2''' termeni: '''1''' şi '''1 (1 + 1)(1 + 1) = 2 * 2 = 4'''
== Rezolvare == 
<syntaxhighlight lang="python" line>

def validare_date(T, A_list):
    for a in A_list:
        if a < 2 or a > 2000000000:
            return False
    if T < 1 or T > 500:
        return False
    else:
        return True

def desc(n):
    cnt = 0
    d = 2
    while n > 1:
        p = 0
        while n % d == 0:
            n //= d
            p += 1
        cnt += p
        d += 1
        if d * d > n:
            d = n
    return cnt

if __name__ == '__main__':
    with open('grea.in', 'r') as fin:
        T = int(fin.readline().strip())
        A_list = [int(fin.readline().strip()) for _ in range(T)]

    if not validare_date(T, A_list):
        fout.write("Datele nu corespund restrictițiilor impuse.")
        exit()

    with open('grea.out', 'w') as fout:
        for a in A_list:
            k = desc(a)
            fout.write("Datele sunt introduse corect.\n")
            fout.write(str(k) + '\n')

</syntaxhighlight>

== Explicație rezolvare==
Funcția validate(T, A_list) verifică dacă datele din fișierul de intrare corespund restricțiilor impuse . Dacă datele nu corespund, funcția va returna False și se va afișa mesajul "Datele nu corespund restrictițiilor impuse.".<br>Funcția desc(n) calculează numărul de factori primi ai unui număr n dat pentru a putea găsi numarul cerut K. Algoritmul este următorul: se împarte n la toți factorii primi mai mici sau egali cu radicalul pătrat al lui n (acesta este cel mai mare factor prim posibil), numărând de fiecare dată câte divizori primi ai lui n se împart la fiecare factor prim găsit. Apoi, se crește d la următorul număr prim și se repetă procesul până când d * d > n. În final, se adaugă numărul de divizori primi găsiți la un contor și se returnează acesta.
În funcția main, fișierul de intrare "grea.in" este deschis, se citesc T și A_list, iar apoi se verifică dacă datele sunt corecte utilizând funcția validate(T, A_list). Dacă datele sunt corecte, se deschide fișierul de ieșire "grea.out" și se calculează K pentru fiecare A din A_list, apoi se afișează numărul K în fișierul de ieșire. Dacă datele nu sunt corecte, programul se va opri cu mesajul "Datele nu corespund restrictițiilor impuse." în fișierul de ieșire.