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

<syntaxhighlight lang="python" line>

1. 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")

1. 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.")

</syntaxhighlight>