4300 - Secv Fb

Cerinţa

Se citește un număr N, un număr K și apoi un șir cu N numere naturale. Determinați câte secvențe de lungime exact K au elementele distincte. Prin secvență înțelegem un set de elemente aflate pe poziții consecutive.

Date de intrare

Pe prima linie a fișierului secv_fbin.txt se găsesc două numere naturale, separate prin exact un spațiu, N și K. Pe linia a doua se găsesc cele N numere ale șirului, separate prin câte un spațiu.numere întregi separate prin spaţii.

Date de ieşire

Pe prima linie a fișierului secv_fbout.txt se găsește un număr natural ce reprezintă valoarea cerută.

Restricții și precizări

• 2 ⩽ N ⩽ 100.000;
• Pentru 20 de puncte K = 2;
• Pentru alte 20 de puncte K = 3;
• Pentru alte 20 de puncte 4 ⩽ K ⩽ 10;
• Pentru alte 20 de puncte, 10 < K ⩽ n-1 și valorile din șir ⩽ 100.000;
• Pentru restul testelor 10 < K ⩽ n-1 și valorile din șir ⩽ 2.000.000.000;

Exemplul 1

secv_fbin.txt

8 3
3 2 4 3 4 5 6 7

sortcif2out.txt

Datele de intrare corespund restrictiilor impuse
5

Exemplul 2

secv_fbin.txt

jfgjfkljd

sortcif2out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, k_validare, numere_validare):
    if n_validare < 2 or n_validare > 100000:
        raise ValueError
    if k_validare < 2 or k_validare > n_validare:
        raise ValueError
    if k_validare == 2 or k_validare == 3 or (4 <= k_validare <= 10) or (10 < k_validare <= n_validare - 1):
        for numar in numere_validare:
            if numar < 1 or numar > 100000:
                raise ValueError
    else:
        for numar in numere_validare:
            if numar < 1 or numar > 2000000000:
                raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


# Funcția secvente_distincte calculează câte secvențe de lungime exact K au elementele distincte
def secvente_distincte(numere, k):
    raspunsuri = 0
    for i in range(len(numere) - k + 1):
        if len(set(numere[i:i+k])) == k:
            raspunsuri += 1
    return raspunsuri


if __name__ == '__main__':
    file_in = open("secv_fbin.txt", "r")
    file_out = open("secv_fbout.txt", "w")

    try:
        # Citim numărul de numere și lungimea secvenței
        n_main, k_main = map(int, file_in.readline().split())
        # Citim numerele
        numere_main = list(map(int, file_in.readline().split()))
        # Validăm datele de intrare
        validare(n_main, k_main, numere_main)
        # Calculăm câte secvențe de lungime exact K au elementele distincte
        raspuns = secvente_distincte(numere_main, k_main)
        # Scriem răspunsul în fișierul de ieșire
        file_out.write(str(raspuns) + '\n')

    # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
    # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")