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

<syntaxhighlight lang="python" line="1">

1. 3763 - Puternic

import math

1. 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

1. 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])

1. 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

1. 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)
              

</syntaxhighlight>

Explicatie

Funcția valideaza_intrare(C: int, N: int, nums: list[int]) -> bool Această funcție primește trei parametri de intrare:

C este un întreg care indică tipul de interogare pe care trebuie să o efectuăm (1 sau 2) N este un întreg care indică numărul de numere întregi din lista nums nums este o listă de N numere întregi, care sunt subiectul interogării Funcția verifică dacă datele de intrare sunt valide și returnează True dacă sunt, altfel returnează False. Pentru a fi considerate valide, datele de intrare trebuie să îndeplinească următoarele condiții:

C trebuie să fie 1 sau 2 N trebuie să fie între 1 și 100.000 Lista nums trebuie să conțină exact N elemente și toate elementele trebuie să fie numere întregi între 1 și 1.000.000.000.

Funcția rezolva(C: int, N: int, nums: list[int]) -> str Această funcție primește aceiași trei parametri ca și funcția valideaza_intrare(). Funcția rezolvă problema specificată în enunț în funcție de tipul de interogare C, folosindu-se de celelalte două funcții (este_puternic() și concateneaza()) și returnează un șir de caractere care reprezintă rezultatul problemei.

Dacă C este 1, funcția numără numerele puternice din lista nums și returnează numărul rezultat. Dacă C este 2, funcția elimină din lista nums toate numerele puternice și numerele cu valoarea 1, apoi formează toate perechile posibile de numere rămase, concatenând fiecare pereche și verificând dacă numărul obținut este puternic. Dacă există cel puțin o astfel de pereche, funcția returnează o listă de perechi de numere care satisfac condiția, altfel returnează valoarea "-1".

Funcția este_puternic(nr: int) -> bool Această funcție primește un singur parametru, nr, care este un număr întreg. Funcția verifică dacă numărul nr este puternic și returnează True dacă este și False în caz contrar.

Un număr este puternic dacă toți factorii lui primi sunt ridicați la puterea cel puțin 2 sau dacă este pătrat perfect sau cub perfect. Această funcție utilizează metoda descompunerii în factori primi pentru a verifica dacă toți factorii primi ai numărului nr au exponența mai mare sau egală cu 2. Funcția concateneaza(a: int, b: int) -> int Această funcție primește două numere întregi a și b și le concatenează într-un singur număr. De exemplu, dacă a este 1234 și b este 5678, atunci concateneaza(a, b) va returna numărul 12345678.

Funcția main() Această funcție nu primește niciun parametru, dar conține codul care citește datele de intrare din fișierul puternic.in, validează datele folosind funcția valideaza_intrare(), apoi calculează rezultatul utilizând funcția rezolva().

Dacă datele de intrare sunt invalide, funcția afișează un mesaj corespunzător. În caz contrar, funcția scrie rezultatul în fișierul puternic.out și afișează un mesaj de confirmare.

Este important de menționat că această implementare folosește tipuri de date și anotări de tipuri, care sunt specifice Python-ului. De asemenea, codul este scris într-un stil modular, care face ca fiecare funcție să aibă un singur scop și să fie ușor de înțeles și de testat.