0523 - SecvEgale

Sursa: 0523 - SecvEgale

---

Cerinţa

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

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.

Restricţii şi precizări

• 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

Intrare

10

5 5 1 1 1 1 2 2 2 2

Ieșire

7 10

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0523 - SecvEgale

def citire_date():

   n = int(input())
   v = []
   for i in range(n):
       v.append(int(input()))
   return v

def rezolvare(v):

   st, dr = 0, 0
   max_lungime = 0
   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

def validare(v):

   return len(v) > 0 and all(isinstance(x, int) for x in v)

if __name__ == "__main__":

   v = citire_date()
   if validare(v):
       st, dr = rezolvare(v)
       print(st + 1, dr + 1)
   else:
       print("Date de intrare invalide.")

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