Vizualizare sursă pentru „0522 - kSecventa1”

Sursa: [https://www.pbinfo.ro/probleme/522/ksecventa1 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.".