0522 - kSecventa1: Difference between revisions

Latest revision as of 20:02, 14 May 2023

Cerinţa[edit | edit source]

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[edit | edit source]

Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire[edit | edit source]

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[edit | edit source]

1 ≤ k < n ≤ 1000, k este divizor al lui n
cele n numere citite vor fi mai mici decât 1000

Exemplu 1[edit | edit source]

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[edit | edit source]

Intrare: 12 5; 2 3 1 1 4 3 1 1 4 3 8 8
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare[edit | edit source]

Rezolvare ver. 1[edit | edit source]

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[edit | edit source]

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

@@ Line 25: / Line 25: @@
 ; Ieșire
 : Datele nu corespund restricțiilor impuse.
-: 3 5
 == Rezolvare ==
@@ Line 31: / Line 31: @@
 <syntaxhighlight lang="python" line>
 # 0522 - kSecventa1
-def citire_date():
-    n = int(input())
-    k = int(input())
-    v = list(map(int, input().split()))
-    return n, k, v
 def gaseste_secvente_identice(n, k, v):
-     secvente = {}
+     if n % k != 0:
-     for i in range(n - k + 1):
+        return "Datele nu corespund restricțiilor impuse."
-         secventa = tuple(v[i:i+k])
-        if secventa in secvente:
+     for i in range(0, n-k+1):
-            return secvente[secventa], i
+         if v[i:i+k] in [v[j:j+k] for j in range(i+1, n-k+1)]:
-        else:
+             return f"{i+1} {v.index(v[i:i+k], i+1)+1}"
-             secvente[secventa] = i
-    return "NU"
+     return "Nu exista secvente identice."
-def valideaza(n, k, v):
-     if n <= k:
-        return "NU"
-     return " ".join(str(i) for i in gaseste_secvente_identice(n, k, v))
+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, v = citire_date()
+     n, k = map(int, input().split())
-     rezultat = valideaza(n, k, v)
+    v = list(map(int, input().split()))
-    if rezultat != "NU":
+     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.")
-    print(rezultat)
 </syntaxhighlight>
 == Explicatie Rezolvare ==
-Funcția citire_date() primește input-ul și returnează cele trei variabile citite.
-Funcția gaseste_secvente_identice(n, k, v) primește dimensiunea vectorului n, lungimea secvențelor k și vectorul v, și returnează o pereche de numere care reprezintă pozițiile de început ale celor două secvențe identice sau un string "NU" în caz contrar. Pentru a găsi secvențele identice, se parcurg toate secvențele de lungime k din vector, iar pentru fiecare se construiește un tuplu și se verifică dacă apare într-un dicționar de secvențe întâlnite anterior. Dacă apare, se returnează pozițiile celor două secvențe identice, altfel se adaugă tuplul în dicționar.
+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(n, k, v) primește aceleași trei variabile și returnează "NU" dacă n<=k sau rezultatul funcției gaseste_secvente_identice(n, k, v) altfel. Dacă există două secvențe identice, se întorc pozițiile lor, altfel se întoarce string-ul "NU".
-Blocul if __name__ == "__main__": este necesar pentru a permite rularea funcțiilor din consolă. În acest bloc se citesc datele de intrare, se validează și se afișează rezultatul.
+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.".