2629 - H3
Enunt[edit | edit source]
Tocmai ai primit cadou de ziua ta un șir de numere naturale a[1], a[2], …, a[n]. Ca să te simți împlinit, trebuie să determini lungimea maximă a unei secvențe cu proprietatea că oricare două valori din secvență sunt distincte.
Cerinta[edit | edit source]
Determină lungimea maximă cerută și anul viitor vei mai primi un șir!
Date de intrare[edit | edit source]
Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații.
Date de iesire[edit | edit source]
Programul va afișa pe ecran lungimea maximă a secvenței de valori distincte.
Restrictii si precizari[edit | edit source]
- 1 ⩽ n ⩽ 1.000.000
- 0 ⩽ a[i] ⩽ 1.000.000.000
Exemplul 1[edit | edit source]
- Intrare
- 9
- 1 2 1 2 5 6 7 2 9
- Iesire
- Datele introduse corespund restrictiilor impuse
- 5
Exemplul 2[edit | edit source]
- Intrare
- 5
- -10 0 5.2 8 3
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> def lungime_maxima_secventa_distincte(n, vector):
frecvente = dict() stanga = 0 lungime_maxima = 0
for dreapta in range(n): numar = vector[dreapta]
while frecvente.get(numar, 0) > 0: frecvente[vector[stanga]] -= 1 stanga += 1
frecvente[numar] = 1 lungime_maxima = max(lungime_maxima, dreapta - stanga + 1)
return lungime_maxima
def verificare_date_intrare(n, vector):
if not (1 <= n <= 1000000) or len(vector) != n or not all(0 <= numar <= 1000000000 for numar in vector): return False return True
- Citire numar de elemente
n = int(input("Introduceți numărul de elemente: "))
- Citire vector
vector = list(map(int, input("Introduceți elementele vectorului, separate prin spațiu: ").split()))
- Verificare date de intrare
if not verificare_date_intrare(n, vector):
print("Datele introduse nu corespund restricțiilor impuse")
else:
# Calcul și afișare rezultat rezultat = lungime_maxima_secventa_distincte(n, vector) print(f"Lungimea maximă a secvenței de valori distincte este: {rezultat}")
</syntaxhighlight>
Explicatie[edit | edit source]
Secvența de lungime maximă 5 este 1 2 5 6 7.