3637 - Interesting Array - Revision history

Mesarosdenisa at 10:53, 27 December 2023

2023-12-27T10:53:15Z

← Older revision		Revision as of 10:53, 27 December 2023
Line 3:		Line 3:
	Un vector interesant vă așteaptă, oare veți reuși să rezolvați misterul ezoteric?		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.		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.		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.		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.
Line 10:		Line 10:
	== Date de intrare ==		== Date de intrare ==

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

	== Date de iesire ==		== Date de iesire ==

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

	== Restrictii si precizari ==		== Restrictii si precizari ==

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

	== Exemplul 1 ==		== Exemplul 1 ==
Line 27:		Line 27:
	:1 2 1 3 2		:1 2 1 3 2
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:2		:2

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

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:51:37Z

Rezolvare

← Older revision		Revision as of 10:51, 27 December 2023
Line 41:		Line 41:
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def cel_mai_interesant_interval(n, vector):		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):		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>		</syntaxhighlight>

Mesarosdenisa: Pagină nouă: == 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 el...

2023-12-16T09:45:09Z

Pagină nouă: == 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 el...

New page

== 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):
frecventa = {} # Dicționar pentru a ține evidența frecvenței fiecărui element în interval
cel_mai_rar = cel_mai_frecvent = vector[0]
grad_interes_maxim = 0

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

# Actualizează frecvența elementului
frecventa[numar] = frecventa.get(numar, 0) + 1

# Actualizează cel mai rar și cel mai frecvent element
if frecventa[numar] > frecventa[cel_mai_frecvent]:
cel_mai_frecvent = numar
if frecventa[numar] < frecventa[cel_mai_rar]:
cel_mai_rar = numar

# Calculează gradul de interes al intervalului curent
grad_interes = frecventa[cel_mai_rar] * frecventa[cel_mai_frecvent]

# Actualizează gradul de interes maxim
grad_interes_maxim = max(grad_interes_maxim, grad_interes)

return grad_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
rezultat = cel_mai_interesant_interval(n, vector)

# Afișarea rezultatului
print(f"Valoarea celui mai interesant interval este: {rezultat}")

if __name__ == "__main__":
main()

</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.