0522 - kSecventa1

Sursa: 0522 - kSecventa1

---

Cerinţa

Se dă un vector cu n elemente, numere naturale, și un număr k. Să se stabilească dacă în vector există două secvențe de lungime k 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 Programul va afișa pe ecran numerele i j, i < j reprezentând pozițiile de început a două secvențe de lungime k identice, dacă există două astfel de secvențe, 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 1

Intrare

12 5

2 3 1 1 4 3 1 1 4 3 8 8

Ieșire

Datele sunt introduse corect.

2 6

Exemplu 2

Intrare

12 5

2 3 1 1 4 3 1 1 4 3 8 8

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 0522 - kSecventa1
def gaseste_secvente_identice(n, k, v):
    if n % k != 0:
        return "Datele nu corespund restricțiilor impuse."
    
    for i in range(0, n-k+1):
        if v[i:i+k] in [v[j:j+k] for j in range(i+1, n-k+1)]:
            return f"{i+1} {v.index(v[i:i+k], i+1)+1}"
    
    return "Nu exista secvente identice."

def valideaza_date_intrare(n, k, v):
    if not (1 <= k < n <= 1000 and n % k == 0):
        return False
    if any(x >= 1000 for x in v):
        return False
    return True
if __name__ == "__main__":
    n, k = map(int, input().split())
    v = list(map(int, input().split()))
    
    if valideaza_date_intrare(n, k, v):
        print("Datele sunt introduse corect.")
        print(gaseste_secvente_identice(n, k, v))
    else:
        print("Datele nu corespund restricțiilor impuse.")

Explicatie Rezolvare

Funcția gaseste_secvente_identice primește trei argumente: n - numărul de elemente din șirul dat, k - lungimea secvenței identice și v - șirul de numere. Dacă n nu este un multiplu de k, funcția returnează un mesaj de eroare. Apoi, cu ajutorul două loop-uri, caută toate secvențele de lungime k și le compară cu toate secvențele de lungime k din dreapta sa. Dacă găsește o secvență identică, returnează pozițiile unde a fost găsită. Dacă nu găsește nicio secvență identică, funcția returnează un mesaj corespunzător.

Funcția valideaza_date_intrare primește aceleași argumente ca și gaseste_secvente_identice și verifică dacă datele de intrare corespund cerințelor problemei. Dacă nu respectă aceste condiții, funcția returnează False. Altfel, returnează True.

În if __name__ == "__main__": se citește de la tastatură valorile lui n, k și șirul v. Apoi, se verifică dacă datele sunt introduse corect cu ajutorul funcției valideaza_date_intrare. Dacă da, se afișează mesajul "Datele sunt introduse corect." și se apelează funcția gaseste_secvente_identice. Dacă nu, se afișează mesajul "Datele nu corespund restricțiilor impuse.".