2384 - Divigrup

Cerinţa

Un șir de numere aparțin unui divigrup dacă au același număr de divizori. Scrieți un program care citește un număr natural N și apoi N numere naturale nenule și care determină:

a. câte divigrupuri există în șirul de numere citite b. numărul de numere din fiecare divigrup, urmat de numerele ce aparțin acestuia, în ordine crescătoare.

Date de intrare

Fișierul de intrare divigrupin.txt 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 divigrupout.txt va conține pe prima linie numărul K, reprezentând numărul de divigrupuri ce se pot forma cu numerele de pe a doua linie a fișierului de intrare. Pe următoarele K rânduri se vor descrie divigrupurile în ordine descrescătoare a numărului de divizori ai elementelor ce le aparțin, astfel încât fiecare rând va avea următoarea structură: M – numărul de elemente ale divigrupului – x1 x2 x3 … xM – numerele aparținând divigrupului, în ordine crescătoare. Valorile scrise pe un rând vor fi separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 200
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1000000000

Exemplul 1

divigrupin.txt

11

21 99 15 9 24 100 45 28 44 4 36

divigrupout.txt

Datele introduse corespund restricțiilor impuse.

5

2 36 100

1 24

4 28 44 45 99

2 15 21

2 4 9

Exemplul 2

divigrupin.txt

300

21 99 15 9 24 100 45 28 44 4 36

divigrupout.txt

Datele introduse nu corespund restricțiilor impuse.

Explicație

Există 5 divigrupuri care sunt descrise pe următoarele 5 rânduri: primul divigrup format din 36 și 100, care au același număr maxim de divizori, următorul divigrup are un singur element, pe 24 care are 8 divizori, al treilea divigrup format din 28, 44, 45 și 99 are 4 elemente, toate având 6 divizori, șamd.

Rezolvare

<syntaxhighlight lang="python" line> import math

def validare(numar_elemente1, lista_numere1): # functia de validare a datelor de intrare

   if numar_elemente1 < 1 or numar_elemente1 > 200:
       raise ValueError
   for numar in lista_numere1:
       if numar < 1 or numar > 1000000000:
           raise ValueError

def calculeaza_numar_divizori(numar): # functia numar_divizori calculează numărul de divizori ai unui număr.

   numar_divizori1 = 0
   for i in range(1, int(math.sqrt(numar)) + 1):
       if numar % i == 0:
           if numar / i == i:
               numar_divizori1 += 1
           else:
               numar_divizori1 += 2
   return numar_divizori1

def divigrupuri(lista_numere1): # functia divigrupuri grupează numerele din șir în funcție de numărul lor de divizori.

   grupuri_divizori1 = {}
   for numar in lista_numere1:
       numar_divizori1 = calculeaza_numar_divizori(numar)
       if numar_divizori1 not in grupuri_divizori1:
           grupuri_divizori1[numar_divizori1] = []
       grupuri_divizori1[numar_divizori1].append(numar)
   for numar_divizori1 in grupuri_divizori1:
       grupuri_divizori1[numar_divizori1].sort()
   return grupuri_divizori1

if __name__ == '__main__':

   file_in = open("divigrupin.txt", "r")         # declararea fisierelor
   file_out = open("divigrupout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       numar_elemente = int(file_in.readline())   # citirea numărului se face ca sir de caractere deoarece e prea mare
       lista_numere = list(map(int, file_in.readline().split()))

       validare(numar_elemente, lista_numere)                 # apelul functiei de validare
       file_out.write("Datele de intrare corespund restrictiilor impuse\n")
       grupuri_divizori = divigrupuri(lista_numere)  # apelul functiei de rezolvare

       file_out.write(str(len(grupuri_divizori)) + "\n")
       for numar_divizori in sorted(grupuri_divizori.keys(), reverse=True):
           file_out.write(str(len(grupuri_divizori[numar_divizori])) + " ")
           file_out.write(" ".join(map(str, grupuri_divizori[numar_divizori])) + "\n")

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>