0521 - kSecventa

Cerinţa

Se dă un vector cu n elemente, numere naturale, și un număr k, divizor al lui n. Se împarte vectorul în k secvențe disjuncte, numerotate de la 1 la k. Să se stabilească dacă există două secvențe identice.

Date de intrare

Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".== Restricţii şi precizări ==

1 ≤ k < n ≤ 1000, k este divizor al lui n
cele n numere citite vor fi mai mici decât 1000

Exemplu

Intrare: 15 5; 3 6 4 7 6 6 6 4 6 7 6 6 4 4 5
Ieșire: Datele nu corespund restricțiilor impuse.; 2 4

Rezolvare

Rezolvare ver. 1

0521 - kSecventa

def citire_date():

   n, k = map(int, input().split())
   x = list(map(int, input().split()))
   return n, k, x

def numar_secvente(n, k, x, t):

   counter = 0
   for i in range(n-k+1):
       secventa = x[i:i+k]
       if all(e <= t for e in secventa):
           counter += 1
   return counter

def valideaza_datele_de_intrare(n, k, x):

   if not (1 <= k <= n <= 100000 and all(0 < i < 1000000000 for i in x)):
       print("Datele nu corespund restricțiilor impuse.")
       exit()

if __name__ == '__main__':

   n, k, x = citire_date()
   t = int(input())
   valideaza_datele_de_intrare(n, k, x)
   rezultat = numar_secvente(n, k, x, t)
   print("Datele sunt introduse corect.")
   print(rezultat)

</syntaxhighlight>

Explicatie Rezolvare

Citim datele de intrare (n, k și vectorul x). Calculăm lungimea fiecărei secvențe (l), care este egală cu n/k. Inițializăm un dicționar (seq_dict) în care vom stoca fiecare secvență și numărul de apariții a acesteia. Iterăm prin fiecare secvență (de la 1 la k) și: a. Extragem secvența corespunzătoare. b. Dacă secvența nu există deja în dicționar, o adăugăm cu valoarea 1. c. Dacă secvența există deja în dicționar, o incrementăm cu 1. d. Verificăm dacă secvența a fost întâlnită de două ori și, dacă da, afișăm index-urile secvențelor identice și ieșim din program. Dacă nu am găsit două secvențe identice, afișăm "NU".