0524 - SecvEgale1
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>
- 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ță.
Regenerate response