Editing 3763 - Puternic

==Cerința==

Un număr puternic este un număr natural mai mare decât 1 care are proprietatea că dacă este divizibil cu numărul prim p atunci este divizibil și cu p^2. De exemplu, 36 și 27 sunt numere puternice, în timp ce 12 nu este număr puternic deoarece este divizibil cu 3 și nu este divizibil cu 3^2. La ora de matematică elevii au aflat ce înseamnă un număr puternic. Pentru a verifica dacă elevii au înțeles, domnul profesor a scris pe tablă un șir de N numere naturale X1, X2, …, XN și l-a rugat pe Mihai să șteargă din șir numerele puternice.

Analizând numerele rămase, Mihai a observat că se poate obține un număr puternic prin concatenarea a două numere din șirul rămas, numere egal depărtate de capetele acestui nou șir. Concatenarea presupune lipirea numărului din a doua jumătate a șirului la finalul celui aflat în prima jumătate. Dacă noul șir are număr impar de elemente, elementul din mijloc se ignoră. De exemplu, dacă șirul obținut după ștergerea numerelor puternice este: 12, 1, 19, 13, 3, 21, 5 atunci numerele obținute prin concatenare sunt 125, 121, 193.
Scrieți un program care citește un număr natural N și apoi un șir de N numere naturale și determină:

Câte numere puternice sunt în șirul dat;
Care sunt perechile de numere din șirul rămas după ștergerea numerelor puternice, numere egal departate de capetele șirului, prin concatenarea cărora se obține un număr puternic.
== Date de intrare ==

Fișierul de intrare '''puternic.in''' conține pe prima linie un număr natural '''C'''. Pentru toate testele de intrare, numărul '''C''' poate avea doar valoarea 1 sau 2. Pe a doua linie a fișierului se găsește numărul natural '''N'''. Pe a treia linie se găsesc '''N''' numere naturale separate prin câte un spațiu.

== Date de ieșire ==

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Dacă '''C = 1''', se va rezolva cerința 1. În acest caz, fișierul de ieșire '''puternic.out''' va conține pe prima linie un număr natural reprezentând numărul de numere puternice din șirul dat.

Dacă '''C = 2''', se va rezolva cerința 2 În acest caz, fișierul de ieșire puternic.out va conține perechile de numere egal depărtate de capetele șirului obținut după ștergere, prin concatenarea cărora de obține un număr puternic. Fiecare pereche se scrie pe câte un rând, iar numerele din pereche se scriu separate printr-un spațiu, primul număr fiind cel din stânga. Dacă sunt mai multe astfel de perechi se vor afișa, în ordine, începând cu cea apropiată de capetele noului șir. Dacă nu există nicio astfel de pereche, în fișierul puternic.out se va afișa -1. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

== Restricţii şi precizări ==
*1 ≤ N ≤ 100.000
*1 ≤ X1, X2, …, XN ≤ 1.000.000.000
== Exemple ==
===Exemplul 1===
; ''puternic.in''
:2
:11
:12 9 1 8 19 6 3 4 49 21 5
; ''ecran''
:Datele sunt introduse corect.
; ''puternic.out''
:12 5
:1 21

===Exemplul 2===
; ''puternic.in''
:1
:8
:100 28 16 11 484 25 162 27
; ''ecran''
:Datele sunt introduse corect.
; ''puternic.out''
:5
===Exemplul 3===
; ''puternic.in''
:2
:5
:1 2 3 4 5 6
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''puternic.out''
:
<br>


== Rezolvare == 
<syntaxhighlight lang="python" line="1">
# 3763 - Puternic
import math


# Funcția de validare a datelor de intrare
# Funcția de validare a datelor de intrare
def validate_input(C: int, N: int, nums: list[int]) -> bool:
    # Verificăm că C este 1 sau 2
    if C not in [1, 2]:
        return False

    # Verificăm că N este între 1 și 100.000
    if not (1 <= N <= 100000):
        return False

    # Verificăm că lista nums are lungimea N și conține doar numere întregi între 1 și 1.000.000.000
    if len(nums) != N or not all(isinstance(x, int) and 1 <= x <= 1000000000 for x in nums):
        return False

    return True


# Funcția de rezolvare
def solve(C: int, N: int, nums: list[int]) -> str:
    # Cazul 1
    if C == 1:
        nrp = 0
        for x in nums:
            if x > 1 and is_powerful(x):
                nrp += 1
        return str(nrp)

    # Cazul 2
    new_nums = []
    for x in nums:
        if x == 1 or not is_powerful(x):
            new_nums.append(x)

    result = []
    for i in range(len(new_nums) // 2):
        nr1 = new_nums[i]
        nr2 = new_nums[-i - 1]
        lp = concat(nr1, nr2)
        if is_powerful(lp):
            result.append((nr1, nr2))

    if not result:
        return "-1"
    else:
        return "\n".join([f"{nr1} {nr2}" for nr1, nr2 in result])


# Funcția de concatenare și verificare dacă numărul obținut este puternic
def is_powerful(nr: int) -> bool:
    # Calculăm descompunerea în factori primi și verificăm dacă toți au exponența mai mare sau egală cu 2
    i = 2
    while i * i <= nr:
        ex = 0
        while nr % i == 0:
            ex += 1
            nr //= i
        if ex == 1:
            return False
        i += 1
    if nr > 1:
        ex = 1
    if ex == 1:
        return False

    # Verificăm dacă nr este pătrat perfect sau cub perfect
    sqrt_nr = round(math.sqrt(nr))
    if sqrt_nr * sqrt_nr == nr:
        return True
    cub_rt = round(nr ** (1 / 3))
    if cub_rt * cub_rt * cub_rt == nr:
        return True
    return False


# Funcția de concatenare a două numere întregi
def concat(a: int, b: int) -> int:
    s = str(a) + str(b)
    return int(s)


# Funcția main care citește și afișează datele din fișiere
# Funcția main care citește și afișează datele din fișiere
if __name__ == "__main__":
    with open("puternic.in", "r") as fin:
        with open("puternic.out", "w") as fout:
            C = int(fin.readline().strip())
            N = int(fin.readline().strip())
            nums = list(map(int, fin.readline().strip().split()))

            if not validate_input(C, N, nums):
                 print ("Datele nu corespund restricțiilor impuse.")
            else:
                print ("Datele sunt introduse corect.\n")
                if C == 1:
                    nrp = 0
                    for x in nums:
                        if x > 1 and is_powerful(x):
                            nrp += 1
                    fout.write(str(nrp))
                elif C == 2:
                    new_nums = []
                    for x in nums:
                        if x == 1 or not is_powerful(x):
                            new_nums.append(x)

                    result = []
                    for i in range(len(new_nums) // 2):
                        nr1 = new_nums[i]
                        nr2 = new_nums[-i - 1]
                        lp = concat(nr1, nr2)
                        if is_powerful(lp):
                            result.append((nr1, nr2))

                    if not result:
                        fout.write("-1")
                    else:
                        fout.write("\n".join([f"{nr1} {nr2}" for nr1, nr2 in result]))










</syntaxhighlight>

==Explicatie==

is_powerful(nr: int) -> bool: Funcția primește un număr întreg nr și returnează o valoare booleană care indică dacă nr este un număr puternic sau nu.

concat(a: int, b: int) -> int: Funcția primește două numere întregi a și b și returnează un număr întreg obținut prin concatenarea lor.

validate_input(C: int, N: int, nums: List[int]) -> bool: Funcția primește trei parametri, C, N și nums, și verifică dacă aceștia respectă restricțiile impuse de cerință. Returnează True dacă datele de intrare sunt valide și False în caz contrar.

solve(C: int, N: int, nums: List[int]) -> str: Funcția primește trei parametri, C, N și nums, și calculează rezultatul corespunzător valorii lui C. Returnează rezultatul sub forma unei șiruri de caractere.

main(): Funcția citeste datele de intrare din fișierul puternic.in, validează datele, calculează rezultatul și afișează rezultatul în fișierul puternic.out.