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