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

Rezolvare

# 3763 - Puternic
import math


# Funcția de validare a datelor de intrare
def valideaza_intrare(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 rezolva(C: int, N: int, nums: list[int]) -> str:
    # Cazul 1
    if C == 1:
        nrp = 0
        for x in nums:
            if x > 1 and este_puternic(x):
                nrp += 1
        return str(nrp)

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

    result = []
    for i in range(len(nums_noi) // 2):
        nr1 = nums_noi[i]
        nr2 = nums_noi[-i - 1]
        lp = concateneaza(nr1, nr2)
        if este_puternic(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 verificare dacă un număr este puternic
def este_puternic(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 concateneaza(a: int, b: int) -> int:
    s = str(a) + str(b)
    return int(s)

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 valideaza_intrare(C, N, nums):
                 print("Datele nu corespund restricțiilor impuse.")
            else:
                print("Datele sunt introduse corect.\n")
                rezultat = rezolva(C, N, nums)
                fout.write(rezultat)

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.