3637 - Interesting Array
Cerinta[edit | edit source]
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[edit | edit source]
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.
Date de iesire[edit | edit source]
Programul va afișa pe ecran numărul S, reprezentând valoarea celui mai interesant interval.
Restrictii si precizari[edit | edit source]
- 1 ⩽ n ⩽ 100000
- cele n numere citite sunt cuprinse între 1 și n.
- Pentru 20 de puncte, 1 ⩽ n ⩽ 2000
Exemplul 1[edit | edit source]
- Intrare
- 5
- 1 2 1 3 2
- Iesire
- Datele introduse corespund restrictiilor impuse
- 2
Exemplul 2[edit | edit source]
- Intrare
- 5
- 0,1,-3,-29,3.9
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<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[edit | edit source]
Î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.