0524 - SecvEgale1

From Bitnami MediaWiki
Revision as of 19:55, 17 April 2023 by Flaviu (talk | contribs)

Sursa: 0524 - SecvEgale1


Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Dacă în vector există mai multe secvențe corecte de lungime maximă se va determina cea mai din stânga.

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 1.000.000.000
  • indexarea elementelor vectorului începe de la 1.

Exemplu

Intrare
12
6 6 8 3 6 6 3 8 4 3 3 4
Ieșire
4 11

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 0524 - SecvEgale1

def citeste_date_intrare():

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


def determina_secventa_maxima(v):

   st, dr = -1, -1
   for i in range(n):
       if v[i] == v[0]:
           j = i
           while j < n and v[j] == v[i]:
               j += 1
           if j - i > dr - st:
               st, dr = i, j - 1
   return st, dr


def valideaza_datele_intrare(v):

   return len(v) > 0


if __name__ == '__main__':

   v = citeste_date_intrare()
   if valideaza_datele_intrare(v):
       n = len(v)
       st, dr = determina_secventa_maxima(v)
       if st == -1 and dr == -1:
           print("NU")
       else:
           print(st + 1, dr + 1)
   else:
       print("Date de intrare invalide.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția citeste_date_intrare citește de la tastatură numerele n și elementele vectorului v și le returnează ca o listă de întregi.

Funcția determina_secventa_maxima primește vectorul v și returnează indicii st și dr ai capetelor secvenței determinate.

Funcția valideaza_datele_intrare primește vectorul v și returnează True dacă datele de intrare sunt valide și False altfel. În acest caz, verificăm doar dacă vectorul nu este gol.

În funcția main, mai întâi citim datele de intrare și verificăm dacă sunt valide. Apoi, determinăm secvența maximă și afișăm indicii capetelor secvenței sau mesajul "NU", dacă nu există nicio secvență.