0521 - kSecventa

Sursa: 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)

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