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

#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


# 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()))

# Rezolvarea problemei
rezultat = rezolva_problema(c, n, arr)

# Scrierea rezultatului în fișierul de ieșire
with open("fortaout.txt", "w") as file:
    file.write(str(rezultat))