3637 - Interesting Array: Difference between revisions

Revision as of 10:51, 27 December 2023

Cerinta

Un vector interesant vă așteaptă, oare veți reuși să rezolvați misterul ezoteric?

Se dă un vector cu n numere. În acest vector, trebuie aflat intervalul(care poate fi oricare subsecvență cu elemente consecutive din vector) care este cel mai interesant. Măsura gradului de interes al unui interval este dată de produsul dintre A și B, unde A reprezintă frecvența celui mai rar element din interval, iar B reprezintă frecvența celui mai frecvent element din interval.

De exemplu, dacă avem vectorul [1, 3, 2, 3, 1, 2, 3], A = 2 și B = 3, iar gradul de interes este 2 * 3 = 6.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de iesire

Programul va afișa pe ecran numărul S, reprezentând valoarea celui mai interesant interval.

Restrictii si precizari

1 ≤ n ≤ 100000
cele n numere citite sunt cuprinse între 1 și n.
Pentru 20 de puncte, 1 ≤ n ≤ 2000

Exemplul 1

Intrare: 5; 1 2 1 3 2
Iesire
Datele introduse corespund restrictiilor impuse: 2

Exemplul 2

Intrare: 5; 0,1,-3,-29,3.9
Iesire
Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def cel_mai_interesant_interval(n, vector):

   interes_maxim = 0

   for i in range(n):
       frecvente = dict()

       for j in range(i, n):
           numar = vector[j]

           if numar in frecvente:
               frecvente[numar] += 1
           else:
               frecvente[numar] = 1

           A = min(frecvente.values())
           B = max(frecvente.values())

           interes = A * B
           interes_maxim = max(interes_maxim, interes)

   return interes_maxim

Citire numar de elemente

n = int(input("Introduceti numarul de elemente: "))

Citire vector

vector = list(map(int, input("Introduceti elementele vectorului, separate prin spatiu: ").split()))

Calcul si afisare rezultat

rezultat = cel_mai_interesant_interval(n, vector) print(f"Cel mai interesant interval are valoarea: {rezultat}")

</syntaxhighlight>

Explicatie

În exemplu se poate alege fie [1, 2, 1], fie [1, 2, 1, 3, 2] sau [2, 1, 3, 2], toate având cea mai mică frecvență 1 și cea mai mare frecvență 2.

@@ Line 41: / Line 41: @@
 <syntaxhighlight lang="python3" line="1">
 def cel_mai_interesant_interval(n, vector):
-     frecventa = {}  # Dicționar pentru a ține evidența frecvenței fiecărui element în interval
+     interes_maxim = 0
-    cel_mai_rar = cel_mai_frecvent = vector[0]
-    grad_interes_maxim = 0
      for i in range(n):
-         numar = vector[i]
+         frecvente = dict()
-         # Actualizează frecvența elementului
+         for j in range(i, n):
-        frecventa[numar] = frecventa.get(numar, 0) + 1
+            numar = vector[j]
-        # Actualizează cel mai rar și cel mai frecvent element
+            if numar in frecvente:
-        if frecventa[numar] > frecventa[cel_mai_frecvent]:
+                frecvente[numar] += 1
-             cel_mai_frecvent = numar
+             else:
-        if frecventa[numar] < frecventa[cel_mai_rar]:
+                frecvente[numar] = 1
-            cel_mai_rar = numar
-        # Calculează gradul de interes al intervalului curent
+            A = min(frecvente.values())
-        grad_interes = frecventa[cel_mai_rar] * frecventa[cel_mai_frecvent]
+            B = max(frecvente.values())
-        # Actualizează gradul de interes maxim
+            interes = A * B
-        grad_interes_maxim = max(grad_interes_maxim, grad_interes)
+            interes_maxim = max(interes_maxim, interes)
-     return grad_interes_maxim
+     return interes_maxim
-def main():
-    # Citirea datelor de intrare
-    n = int(input("Introduceti numarul n: "))
-    vector = list(map(int, input("Introduceti vectorul de n numere separate prin spatii: ").split()))
-    # Calculul celui mai interesant interval
+# Citire numar de elemente
-    rezultat = cel_mai_interesant_interval(n, vector)
+n = int(input("Introduceti numarul de elemente: "))
-    # Afișarea rezultatului
+# Citire vector
-    print(f"Valoarea celui mai interesant interval este: {rezultat}")
+vector = list(map(int, input("Introduceti elementele vectorului, separate prin spatiu: ").split()))
+# Calcul si afisare rezultat
+rezultat = cel_mai_interesant_interval(n, vector)
+print(f"Cel mai interesant interval are valoarea: {rezultat}")
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>