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 ⩽ N ⩽ 100.000
• 0 ⩽ A[i] ⩽ 1.000.000, 1 ⩽ i ⩽ N
• 0 ⩽ D ⩽ 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

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