2629 - H3 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:29:06Z

Rezolvare

← Older revision		Revision as of 12:29, 29 December 2023
Line 54:		Line 54:

	return lungime_maxima		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		# Citire numar de elemente
	n = int(input("~~Introduceti numarul~~ de elemente: "))		n = int(input("Introduceți numărul de elemente: "))

	# Citire vector		# Citire vector
	vector = list(map(int, input("~~Introduceti~~ elementele vectorului, separate prin ~~spatiu~~: ").split()))		vector = list(map(int, input("Introduceți elementele vectorului, separate prin spațiu: ").split()))

	~~# Calcul si afisare rezultat~~
	~~rezultat = lungime_maxima_secventa_distincte(n, vector)~~
	~~print(f"Lungimea maxima a secventei de valori distincte este: {rezultat}"~~)

			# 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>		</syntaxhighlight>

Mesarosdenisa at 10:56, 27 December 2023

2023-12-27T10:56:09Z

← Older revision		Revision as of 10:56, 27 December 2023
Line 1:		Line 1:
	== Enunt ==		== 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 ==		== Cerinta ==
Line 9:		Line 9:
	== Date de intrare ==		== 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 ==		== Date de iesire ==
Line 17:		Line 17:
	== Restrictii si precizari ==		== 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 ==		== Exemplul 1 ==
Line 25:		Line 25:
	:1 2 1 2 5 6 7 2 9		:1 2 1 2 5 6 7 2 9
	;Iesire		;Iesire
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:5		:5

Line 33:		Line 33:
	:-10 0 5.2 8 3		:-10 0 5.2 8 3
	;Iesire		;Iesire
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:54:46Z

Rezolvare

← Older revision		Revision as of 10:54, 27 December 2023
Line 38:		Line 38:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<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		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():~~		# Citire numar de elemente
	# ~~Citirea datelor~~ de ~~intrare~~		n = int(input("Introduceti numarul de elemente: "))
	n = int(input("Introduceti numarul ~~n: "))~~
	~~sir = list(map(int, input("Introduceti sirul~~ de ~~n numere separate prin spatii~~: "~~).split()~~))

	# ~~Calculul lungimii maxime a secvenței distincte~~		# Citire vector
	~~rezultat~~ = ~~lungime_maxima_secventa_distincta~~(n, ~~sir~~)		vector = list(map(int, input("Introduceti elementele vectorului, separate prin spatiu: ").split()))

	# ~~Afișarea rezultatului~~		# Calcul si afisare rezultat
	print(f"Lungimea maxima a secventei de valori distincte este: {rezultat}")		rezultat = lungime_maxima_secventa_distincte(n, vector)
			print(f"Lungimea maxima a secventei de valori distincte este: {rezultat}")

	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: Pagină nouă: == 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. == Cerinta == Determină lungimea maximă cerută și anul viitor vei mai primi un șir! == Date de intrare == Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații. == Dat...

2023-12-16T09:37:35Z

Pagină nouă: == 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. == Cerinta == Determină lungimea maximă cerută și anul viitor vei mai primi un șir! == Date de intrare == Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații. == Dat...

New page

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

== Cerinta ==

Determină lungimea maximă cerută și anul viitor vei mai primi un șir!

== Date de intrare ==

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

== Date de iesire ==

Programul va afișa pe ecran lungimea maximă a secvenței de valori distincte.

== Restrictii si precizari ==

*1 ≤ n ≤ 1.000.000
*0 ≤ a[i] ≤ 1.000.000.000

== Exemplul 1 ==
;Intrare
:9
:1 2 1 2 5 6 7 2 9
;Iesire
;Datele introduse corespund restrictiilor impuse
:5

== Exemplul 2 ==
;Intrare
:5
:-10 0 5.2 8 3
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def lungime_maxima_secventa_distincta(n, sir):
frecventa = {} # Dicționar pentru a ține evidența frecvenței aparițiilor fiecărui număr
lungime_maxima = 0
inceput_secventa = 0

for sfarsit_secventa in range(n):
numar = sir[sfarsit_secventa]

# Dacă numărul a mai fost întâlnit anterior în secvență, actualizează poziția de start a secvenței
if numar in frecventa and frecventa[numar] >= inceput_secventa:
inceput_secventa = frecventa[numar] + 1

# Actualizează frecvența numărului
frecventa[numar] = sfarsit_secventa

# Calculează lungimea maximă a secvenței
lungime_maxima = max(lungime_maxima, sfarsit_secventa - inceput_secventa + 1)

return lungime_maxima

def main():
# Citirea datelor de intrare
n = int(input("Introduceti numarul n: "))
sir = list(map(int, input("Introduceti sirul de n numere separate prin spatii: ").split()))

# Calculul lungimii maxime a secvenței distincte
rezultat = lungime_maxima_secventa_distincta(n, sir)

# Afișarea rezultatului
print(f"Lungimea maxima a secventei de valori distincte este: {rezultat}")

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==

Secvența de lungime maximă 5 este 1 2 5 6 7.