3433 - Forta

Enunț

Forța unui număr natural nenul X este egală cu numărul de divizori pozitivi ai lui X. De exemplu, numărul X = 10 are forţa 4, deoarece 10 are 4 divizori, mulțimea divizorilor fiind D10 = {1,2,5,10}.

Cerința

Scrieţi un program care, cunoscând un șir de n numere naturale nenule, rezolvă următoarele cerințe:

1. determină cel mai mic număr din șir care are forța maximă;
2. determină lungimea maximă a unei secvențe formată din numere cu aceeași forţă ce poate fi obținută prin rearanjarea convenabilă a elementelor din șir.

Date de intrare

Fișierul de intrare fortain.txt conține pe prima linie numărul c, care reprezintă cerința de rezolvat (1 sau 2), pe a doua linie un număr natural n, iar pe următoarea linie n numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire fortaout.txt va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința c.

Restricții și precizări

• 1 ⩽ n ⩽ 100.000
• 1 ⩽ numere din sir ⩽ 2.000.000.000

Exemplul 1

Intrare

fortain.txt

1

6

17 243 10 32 25 13

Ieșire

Datele de intrare corespund restricțiilor impuse

fortaout.txt

32

Explicație

Cerința este 1. D17={1,17}, D243={1,3,9,27,81,243}, D10={1,2,5,10}, D32={1,2,4,8,16,32}, D25={1,5,25}, D13={1,13}. Deci cea mai mare forță este 6, iar numărul minim cu această forță este 32.

Exemplul 2

Intrare

fortain.txt

2

8

121 10 14 25 49 9 25 15

Ieșire

Datele de intrare corespund restricțiilor impuse

5

Explicație

Cerința este 2. O rearanjare a șirului ar putea fi (10 14 15)(121 25 49 9 25) astfel încât putem obține o secvență de lungime 3 de numere de forță 4 și o secvență de lungime 5 de numere de forță 3.

Exemplul 3

Intrare

fortain.txt

2

1000001

121 10 14 25 49 9 25 15

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 3433 - Forta

def valideaza_input(n, arr):

   if 1 <= n <= 100000:
       print("Datele de intrare corespund restricțiilor impuse")
   else:
       print("Datele de intrare NU corespund restricțiilor impuse")
   for x in arr:
       if not (1 <= x <= 2000000000):
           print("Datele de intrare NU corespund restricțiilor impuse")

def numar_divizori(x):

   count = 0
   for i in range(1, x + 1):
       if x % i == 0:
           count += 1
   return count

def min_numar_cu_max_forta(arr):

   min_num = float('inf')
   max_forta = 0

   for num in arr:
       forta = numar_divizori(num)
       if forta > max_forta or (forta == max_forta and num < min_num):
           max_forta = forta
           min_num = num

   return min_num

def lungime_maxima_secventa(arr):

   forta_counts = {}
   lungime_maxima = 0

   for num in arr:
       forta = numar_divizori(num)
       if forta in forta_counts:
           forta_counts[forta] += 1
       else:
           forta_counts[forta] = 1

       lungime_maxima = max(lungime_maxima, forta_counts[forta])

   return lungime_maxima

def rezolva_problema(c, n, arr):

   valideaza_input(n, arr)
   rezultat = 0
   if c == 1:
       rezultat = min_numar_cu_max_forta(arr)
   elif c == 2:
       rezultat = lungime_maxima_secventa(arr)
   else:
       print("Cerința c trebuie să fie 1 sau 2.")

   return rezultat

1. Citirea datelor din fișierul de intrare

with open("fortain.txt", "r") as file:

   c = int(file.readline().strip())
   n = int(file.readline().strip())
   arr = list(map(int, file.readline().strip().split()))

1. Rezolvarea problemei

rezultat = rezolva_problema(c, n, arr)

1. Scrierea rezultatului în fișierul de ieșire

with open("fortaout.txt", "w") as file:

   file.write(str(rezultat))

</syntaxhighlight>