2629 - H3: Difference between revisions

Latest revision as of 12:29, 29 December 2023

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.

@@ Line 1: / Line 1: @@
 == Enunt ==
-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.
+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 ==
@@ Line 9: / Line 9: @@
 == Date de intrare ==
-Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații.
+Programul citește de la tastatură numărul '''n''', apoi șirul de '''n''' numere naturale, separate prin spații.
 == Date de iesire ==
@@ Line 17: / Line 17: @@
 == Restrictii si precizari ==
-*1 ≤ n ≤ 1.000.000
+*1 &les; n &les; 1.000.000
-*0 ≤ a[i] ≤ 1.000.000.000
+*0 &les; a[i] &les; 1.000.000.000
 == Exemplul 1 ==
@@ Line 25: / Line 25: @@
 :1 2 1 2 5 6 7 2 9
 ;Iesire
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :5
@@ Line 33: / Line 33: @@
 :-10 0 5.2 8 3
 ;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def lungime_maxima_secventa_distincta(n, sir):
+def lungime_maxima_secventa_distincte(n, vector):
-     frecventa = {}  # Dicționar pentru a ține evidența frecvenței aparițiilor fiecărui număr
+     frecvente = dict()
+    stanga = 0
      lungime_maxima = 0
-    inceput_secventa = 0
-     for sfarsit_secventa in range(n):
+     for dreapta in range(n):
-         numar = sir[sfarsit_secventa]
+         numar = vector[dreapta]
-         # Dacă numărul a mai fost întâlnit anterior în secvență, actualizează poziția de start a secvenței
+         while frecvente.get(numar, 0) > 0:
-        if numar in frecventa and frecventa[numar] >= inceput_secventa:
+            frecvente[vector[stanga]] -= 1
-             inceput_secventa = frecventa[numar] + 1
+             stanga += 1
-         # Actualizează frecvența numărului
+         frecvente[numar] = 1
-        frecventa[numar] = sfarsit_secventa
+        lungime_maxima = max(lungime_maxima, dreapta - stanga + 1)
-        # Calculează lungimea maximă a secvenței
+    return lungime_maxima
-        lungime_maxima = max(lungime_maxima, sfarsit_secventa - inceput_secventa + 1)
-    return lungime_maxima
-def main():
+def verificare_date_intrare(n, vector):
-     # Citirea datelor de intrare
+     if not (1 <= n <= 1000000) or len(vector) != n or not all(0 <= numar <= 1000000000 for numar in vector):
-    n = int(input("Introduceti numarul n: "))
+        return False
-    sir = list(map(int, input("Introduceti sirul de n numere separate prin spatii: ").split()))
+    return True
-    # Calculul lungimii maxime a secvenței distincte
+# Citire numar de elemente
-    rezultat = lungime_maxima_secventa_distincta(n, sir)
+n = int(input("Introduceți numărul de elemente: "))
-    # Afișarea rezultatului
+# Citire vector
-    print(f"Lungimea maxima a secventei de valori distincte este: {rezultat}")
+vector = list(map(int, input("Introduceți elementele vectorului, separate prin spațiu: ").split()))
-if __name__ == "__main__":
+# Verificare date de intrare
-     main()
+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>