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

<syntaxhighlight lang="python" line>

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

</syntaxhighlight>

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