0523 - SecvEgale: Difference between revisions

Latest revision as of 19:35, 14 May 2023

Cerinţa[edit]

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente egale din vector. Dacă în vector există mai multe secvențe de elemente egale de lungime maximă se va determina cea mai din dreapta.

Date de intrare[edit]

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

Date de ieșire[edit]

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, 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]

1 ≤ n ≤ 1000
cele n numere citite vor fi mai mici decât 1000
indicii elementelor vectorului sunt cuprinși între 1 și n

Exemplu[edit]

Intrare: 10; 5 5 1 1 1 1 2 2 2 2
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare[edit]

Rezolvare ver. 1[edit]

0523 - SecvEgale

def validare(n, v):

   if n < 1 or n > 1000:
       return False
   for x in v:
       if x < 0 or x >= 1000:
           return False
   return True

def rezolvare(n, v):

   if not validare(n, v):
       return "Datele nu corespund restricțiilor impuse."

   maxim = 1
   poz = n - 1
   for i in range(n - 1, 0, -1):
       lungime = 1
       while i > 0 and v[i] == v[i - 1]:
           lungime += 1
           i -= 1
       if lungime > maxim:
           maxim = lungime
           poz = i

   return maxim

if __name__ == "__main__":

   n = int(input())
   v = list(map(int, input().split()))

   rez = rezolvare(n, v)
   if isinstance(rez, str):
       print(rez)
   else:
       print("Datele sunt introduse corect.")
       print(rez)

</syntaxhighlight>

Explicație rezolvare[edit]

Funcția validare primește numărul de elemente n și vectorul v și returnează True dacă acestea corespund restricțiilor impuse și False în caz contrar. Mai precis, verifică dacă n este între 1 și 1000 și dacă toate elementele din v sunt numere naturale mai mici decât 1000. Funcția rezolvare primește numărul de elemente n și vectorul v și returnează lungimea celei mai lungi secvențe de elemente egale din vector. Mai precis, parcurge vectorul de la dreapta la stânga și pentru fiecare element verifică cât de lungă este secvența de elemente egale care începe cu el. Dacă lungimea acestei secvențe este mai mare decât lungimea celei mai lungi secvențe găsite până acum, atunci actualizează variabila maxim și variabila poz care reține poziția primei apariții a celei mai lungi secvențe de elemente egale. În funcția rezolvare se folosește și funcția validare pentru a verifica dacă datele de intrare sunt corecte. În funcția rezolvare se consideră că dacă în vector există mai multe secvențe de elemente egale de lungime maximă, atunci se determină cea mai din dreapta. În funcția rezolvare se folosește funcția isinstance pentru a verifica dacă rezultatul este un șir de caractere (adică mesajul de eroare) sau un număr (adică lungimea celei mai lungi secvențe de elemente egale). Citirea datelor de intrare și afișarea rezultatului se fac în funcția main.

@@ Line 6: / Line 6: @@
 Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului.
 == Date de ieșire ==
-Programul va afișa pe ecran indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu.
+Dacă datele sunt introduse corect, pe ecran se va afișa:
+'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', 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 ≤ n ≤ 1000
@@ Line 16: / Line 17: @@
 : 5 5 1 1 1 1 2 2 2 2
 ; Ieșire
-: 7 10
+: Datele nu corespund restricțiilor impuse.
 == Rezolvare ==
@@ Line 23: / Line 25: @@
 # 0523 - SecvEgale
-def citire_date():
+def validare(n, v):
-     n = int(input())
+     if n < 1 or n > 1000:
-    v = []
+        return False
-     for i in range(n):
+     for x in v:
-         v.append(int(input()))
+         if x < 0 or x >= 1000:
-     return v
+            return False
+     return True
-def rezolvare(v):
+def rezolvare(n, v):
-     st, dr = 0, 0
+     if not validare(n, v):
-    max_lungime = 0
+         return "Datele nu corespund restricțiilor impuse."
-    i = 0
-    while i < len(v):
-         j = i + 1
-        while j < len(v) and v[j] == v[i]:
-            j += 1
-        lungime = j - i
-        if lungime >= max_lungime:
-            max_lungime = lungime
-            st, dr = i, j - 1
-        i = j
-    return st, dr
+    maxim = 1
+    poz = n - 1
+    for i in range(n - 1, 0, -1):
+        lungime = 1
+        while i > 0 and v[i] == v[i - 1]:
+            lungime += 1
+            i -= 1
+        if lungime > maxim:
+            maxim = lungime
+            poz = i
-def validare(v):
+     return maxim
-     return len(v) > 0 and all(isinstance(x, int) for x in v)
 if __name__ == "__main__":
-     v = citire_date()
+     n = int(input())
-     if validare(v):
+     v = list(map(int, input().split()))
-        st, dr = rezolvare(v)
-         print(st + 1, dr + 1)
+    rez = rezolvare(n, v)
+    if isinstance(rez, str):
+         print(rez)
      else:
-         print("Date de intrare invalide.")
+         print("Datele sunt introduse corect.")
+        print(rez)
 </syntaxhighlight>
 == Explicație rezolvare==
-Funcția citire_date() citește de la tastatură numărul n, apoi n numere întregi, reprezentând elementele vectorului v. Acestea sunt stocate în lista v, care este întoarsă la sfârșitul funcției.
+Funcția validare primește numărul de elemente n și vectorul v și returnează True dacă acestea corespund restricțiilor impuse și False în caz contrar. Mai precis, verifică dacă n este între 1 și 1000 și dacă toate elementele din v sunt numere naturale mai mici decât 1000.
-Funcția rezolvare(v) primește ca parametru lista v și determină cea mai lungă secvență de elemente egale din vector, returnând indicii de la început și sfârșit ai acestei secvențe. Algoritmul utilizat este unul clasic de parcurgere a vectorului și ținere a unor variabile auxiliare pentru stocarea lungimii maxime a secvenței, precum și indicii corespunzători.
+Funcția rezolvare primește numărul de elemente n și vectorul v și returnează lungimea celei mai lungi secvențe de elemente egale din vector. Mai precis, parcurge vectorul de la dreapta la stânga și pentru fiecare element verifică cât de lungă este secvența de elemente egale care începe cu el. Dacă lungimea acestei secvențe este mai mare decât lungimea celei mai lungi secvențe găsite până acum, atunci actualizează variabila maxim și variabila poz care reține poziția primei apariții a celei mai lungi secvențe de elemente egale.
-Funcția validare(v) primește ca parametru lista v și verifică dacă aceasta este nevidă și conține doar numere întregi. Verificarea se face cu ajutorul funcției încorporate all() și a expresiei isinstance(x, int).
+În funcția rezolvare se folosește și funcția validare pentru a verifica dacă datele de intrare sunt corecte.
-În blocul if __name__ == "__main__", se citesc datele de intrare cu ajutorul funcției citire_date(), se validează cu funcția validare(v) și se calculează rezultatul cu ajutorul funcției rezolvare(v). Dacă datele de intrare sunt valide, se afișează rezultatul pe ecran, iar dacă nu, se afișează un mesaj corespunzător.
+În funcția rezolvare se consideră că dacă în vector există mai multe secvențe de elemente egale de lungime maximă, atunci se determină cea mai din dreapta.
+În funcția rezolvare se folosește funcția isinstance pentru a verifica dacă rezultatul este un șir de caractere (adică mesajul de eroare) sau un număr (adică lungimea celei mai lungi secvențe de elemente egale).
+Citirea datelor de intrare și afișarea rezultatului se fac în funcția main.