View source for 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ă; <br>
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 &les; '''n''' &les; 100.000
* 1 &les; '''numere din sir''' &les; 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>
#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))


</syntaxhighlight>