Editing 3086 - densitate1

== Enunț ==
Cristi, deja familiarizat cu noțiunea de densitate de la orele de fizică, își propune să o studieze și din perspectiva informaticii. Astfel, el alege un șir de N numere naturale A[1], A[2], …, A[N] și își dorește să experimenteze.

== Cerința ==
Să se calculeze câte secvențe nevide au proprietatea că raportul dintre numărul elementelor pare din cadrul secvenței și lungimea secvenței este exact D.

== Date de intrare ==
În fișierul de intrare densitatein.txt, pe prima linie se află numărul N, ce reprezintă lungimea șirului de numere. Pe a doua linie se află, separate prin câte un spațiu, N numere naturale. Pe a treia linie se află densitatea D, reprezentată cu două zecimale exacte sub forma 0.ab.

== Date de ieșire ==
Fișierul de ieșire densitateout.txt va conține o singură linie pe care se va afla numărul secvențelor ce respectă proprietatea din enunț.

== Restricții și precizări ==
* 1 &les; '''N''' &les; 100.000
* 0 &les; '''A[i]''' &les; 1.000.000, 1 &les; '''i''' &les; N
* 0 &les; '''D''' &les; 0.99

== Exemplul 1 ==
; Intrare
; densitatein.txt
: 6
: 1 0 3 5 2 7
: 0.50
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; densitateout.txt
: 5

=== Explicație ===
Sunt 5 secvențe cu densitate 0.50: 1 0; 0 3; 5 2; 2 7; 0 3 5 2.

== Exemplul 2 ==
; Intrare
; densitatein.txt
: 0
: 1 0 3 5 2 7
: 0.50
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#3086 - Densitate1

def validare_date(n, a, d):
    # Verificăm restricțiile privind lungimea șirului
    if not 1 <= n <= 100000:
        return False, "Lungimea șirului trebuie să fie între 1 și 100.000."

    # Verificăm restricțiile privind elementele șirului
    for elem in a:
        if not 0 <= elem <= 1000000:
            return False, "Elementele șirului trebuie să fie între 0 și 1.000.000."

    # Verificăm restricțiile privind densitatea d
    if not 0 <= d <= 0.99:
        return False, "densitatea trebuie să fie între 0 și 0.99."

    return True, ""


def calculeaza_secvente(n, a, d):
    numar_secvente = 0

    # Parcurgem șirul pentru a genera secvențele
    for i in range(n):
        for j in range(i + 1, n + 1):
            # Extragem secvența curentă
            secventa_curenta = a[i:j]

            # Calculăm densitatea secvenței curente
            densitate_secventa = len([x for x in secventa_curenta if x % 2 == 0]) / len(secventa_curenta)

            # Verificăm dacă densitatea este exact d
            if round(densitate_secventa, 2) == d:
                numar_secvente += 1

    return numar_secvente


# Citim datele din fișierul de intrare
with open("densitatein.txt", "r") as f:
    n = int(f.readline())
    a = list(map(int, f.readline().split()))
    d = float(f.readline())

# Validăm datele
valid, mesaj = validare_date(n, a, d)

# dacă datele sunt valide, rezolvăm problema și scriem rezultatul în fișierul de ieșire
if valid:
    print("Datele de intrare corespund restricțiilor impuse")
    rezultat = calculeaza_secvente(n, a, d)
    with open("densitateout.txt", "w") as f_out:
        f_out.write(str(rezultat))
else:
    print("Datele de intrare NU corespund restricțiilor impuse")

</syntaxhighlight>