0283 - Secventa - Revision history

Flaviu at 21:07, 14 May 2023

2023-05-14T21:07:56Z

← Older revision		Revision as of 21:07, 14 May 2023
Line 28:		Line 28:
	: 6 9		: 6 9

	== Exemplu 1 ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: secventa.in		: secventa.in
Line 34:		Line 34:
	: 1 9 22 13 5 2 5 8 10		: 1 9 22 13 5 2 5 8 10
	; Ieșire		; Ieșire
	~~: secventa.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 42:		Line 41:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 0283 - Secventa		# 0283 - Secventa
	~~def citire():~~
	~~try:~~
	~~with open("secventa.in", "r") as f:~~
	~~n = int(f.readline())~~
	~~a = list(map(int, f.readline().split()))~~
	~~return n, a~~
	~~except:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~print("Datele nu sunt introduse corect.")~~

	def rezolvare(n, a):		def rezolvare(n, a):
	p = u = -1		p = u = -1
Line 81:		Line 70:

	if __name__ == "__main__":		if __name__ == "__main__":
	n, a ~~= citire~~()		try:
	p, u = rezolvare(n, a)		with open("secventa.in", "r") as f:
	if p != -1 and u != -1:		n = int(f.readline())
	print("Datele sunt introduse corect.")		a = list(map(int, f.readline().split()))
	~~else~~:		if n < 1 or n > 100000:
			raise ValueError("Numarul n nu se incadreaza in limitele problemei.")
			for i in range(n):
			if a[i] < 0 or a[i] > 999999999:
			raise ValueError("Elementele sirului trebuie sa fie numere naturale de cel mult 9 cifre.")
			p, u = rezolvare(n, a)
			if p != -1 and u != -1:
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
			validare(p, u)
			except Exception as e:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~validare~~(~~p, u~~)		print(e)



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru rezolvarea~~ acestei ~~probleme~~, ~~vom parcurge şirul dat şi vom folosi~~ două variabile~~: lungimea_secvenţei~~ pentru a ~~memora~~ lungimea ~~secvenţei curente~~, şi suma_elementelor pentru ~~a memora~~ suma elementelor din ~~secvenţa~~ curentă~~. De asemenea~~, ~~vom mai folosi două variabile:~~ max_lungime ~~pentru a memora~~ lungimea ~~maximă găsită~~ până ~~acum~~, ~~şi max_suma pentru a memora~~ suma maximă ~~găsită până acum~~, ~~precum şi două variabile:~~ p ~~pentru a memora poziţia~~ de ~~început a secvenţei maxime şi~~ u ~~pentru a memora poziţia de sfârşit a secvenţei maxime~~.		Funcția de rezolvare, rezolvare(n, a), care primește ca parametri numărul de elemente din șir n și șirul propriu-zis a. Scopul acestei funcții este de a determina cea mai lungă secvență cu proprietatea specificată în enunț și de a returna pozițiile primului și ultimului element din această secvență.

			Această funcție începe prin a inițializa variabilele p și u cu valoarea -1, semnificând faptul că încă nu am găsit nicio secvență cu proprietatea specificată. De asemenea, funcția mai inițializează două variabile max_lungime și max_suma cu valoarea 0, care vor fi folosite pentru a determina secvența maximă în ceea ce privește lungimea și suma elementelor.

			În continuare, se parcurge șirul a și se calculează lungimea și suma elementelor din secvența curentă, utilizând variabilele lungime_secventa și suma_elementelor. Dacă se întâlnește un element cu paritatea identică cu elementul anterior, secvența curentă se întrerupe și se inițializează lungimea și suma elementelor pentru o nouă secvență începând cu elementul curent. În caz contrar, se actualizează lungimea și suma elementelor din secvența curentă, și se compară aceste valori cu cele ale secvenței maximale găsite până în acel moment (max_lungime și max_suma). Dacă lungimea secvenței curente depășește lungimea secvenței maxime găsite până în acel moment, sau are lungime egală cu aceasta dar suma elementelor este mai mare, atunci secvența curentă devine noua secvență maximă și se actualizează variabilele max_lungime și max_suma. În plus, se actualizează și variabilele p și u cu pozițiile primului și ultimului element din secvența curentă, dacă este cazul.

			Funcția de rezolvare returnează apoi variabilele p și u.

	~~În timpul parcurgerii şirului~~, ~~vom actualiza lungimea_secvenţei şi suma_elementelor pentru fiecare secvenţă~~ găsită, ~~şi vom compara~~ cu ~~valorile maxime găsite până acum~~, ~~actualizându~~-le în ~~caz că avem o secvenţă nouă mai bună~~.		Funcția de validare, validare(p, u), primește ca parametri pozițiile primului și ultimului element din secvența maximă găsită de funcția rezolvare, și are rolul de a scrie aceste valori în fișierul de ieșire secventa.out. Dacă nu s-a găsit nicio secvență cu proprietatea specificată, funcția va scrie -1 în fișierul de ieșire.

	~~După parcurgerea întregului şir~~, ~~vom afişa valorile p şi u, adică poziţiile~~ de ~~început şi sfârşit ale secvenţei maxime~~.		În funcția principală if __name__ == "__main__", începem prin citirea datelor de intrare din fișierul `secventa.

Flaviu at 07:50, 3 May 2023

2023-05-03T07:50:58Z

← Older revision		Revision as of 07:50, 3 May 2023
Line 13:		Line 13:
	Fişierul de ieşire secventa.out va conţine		Fişierul de ieşire secventa.out va conţine
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''~~numărul c~~''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 ≤ n ≤ 100.000;		* 1 ≤ n ≤ 100.000;
	* elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;		* elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: secventa.in
	: 10		: 10
	: 2 4 3 6 7 5 2 5 8 10		: 2 4 3 6 7 5 2 5 8 10
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: secventa.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 6 9		: 6 9

			== Exemplu 1 ==
			; Intrare
			: secventa.in
			: 10 2 3 4
			: 1 9 22 13 5 2 5 8 10
			; Ieșire
			: secventa.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:28, 28 April 2023

2023-04-28T14:28:36Z

← Older revision		Revision as of 14:28, 28 April 2023
Line 11:		Line 11:

	== Date de ieșire ==		== Date de ieșire ==
	Fişierul de ieşire secventa.out va conţine pe ~~prima linie două numere p şi u~~, ~~separate printr-~~un ~~spaţiu~~, reprezentând ~~indicele primului~~, ~~respectiv al ultimului element din secvenţa determinată~~.		Fişierul de ieşire secventa.out va conţine
			Dacă datele sunt introduse corect, pe ecran se va afișa:
			'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 21:		Line 23:
	: 2 4 3 6 7 5 2 5 8 10		: 2 4 3 6 7 5 2 5 8 10
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 6 9		: 6 9

Line 28:		Line 32:
	# 0283 - Secventa		# 0283 - Secventa
	def citire():		def citire():
	with open("secventa.in", "r") as f:		try:
	n = int(f.readline())		with open("secventa.in", "r") as f:
	a = []		n = int(f.readline())
	~~for i in range(n):~~		a = list(map(int, f.readline().split()))
	~~a.extend~~(map(int, f.readline().split()))		return n, a
	return n, a		except:
			print("Datele nu corespund restricțiilor impuse.")
			print("Datele nu sunt introduse corect.")

	def rezolvare(n, a):		def rezolvare(n, a):
	p = u = -1 ~~# poziția de început și de sfârșit a secvenței maxime~~		p = u = -1
	max_lungime = max_suma = 0 ~~# lungimea și suma maximă găsite până acum~~		max_lungime = max_suma = 0

	# ~~parcurgem șirul și căutăm secvența~~ maximă		# Cautam secventa maximă
	lungime_secventa = suma_elementelor = 1		lungime_secventa = suma_elementelor = 1
	for i in range(1, n):		for i in range(1, n):
Line 56:		Line 61:

	return p, u		return p, u


	def validare(p, u):		def validare(p, u):
Line 63:		Line 67:
	f.write("-1\n")		f.write("-1\n")
	else:		else:
	f.write(~~str(~~p+1~~) + " " + str(~~u+1~~) + "~~\n")		f.write(f"{p+1} {u+1}\n")


	if __name__ == "__main__":		if __name__ == "__main__":
	n, a = citire()		n, a = citire()
	p, u = rezolvare(n, a)		p, u = rezolvare(n, a)
			if p != -1 and u != -1:
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
	validare(p, u)		validare(p, u)


	</syntaxhighlight>		</syntaxhighlight>

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/283/secventa - Secventa] ---- == Cerinţa == Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite. Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sum...

2023-04-17T20:37:10Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/283/secventa - Secventa] ---- == Cerinţa == Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite. Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sum...

New page

Sursa: [https://www.pbinfo.ro/probleme/283/secventa - Secventa]
----
== Cerinţa ==
Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite.

Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sumă maximă a elementelor se va determina cea mai din dreapta.

== Date de intrare ==
Fişierul de intrare secventa.in conţine pe prima linie numărul n; urmează cele n elemente ale şirului, dispuse pe mai multe linii şi separate prin spaţii.

== Date de ieșire ==
Fişierul de ieşire secventa.out va conţine pe prima linie două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000;
* elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;
== Exemplu ==
; Intrare
: 10
: 2 4 3 6 7 5 2 5 8 10
; Ieșire
: 6 9

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0283 - Secventa
def citire():
with open("secventa.in", "r") as f:
n = int(f.readline())
a = []
for i in range(n):
a.extend(map(int, f.readline().split()))
return n, a

def rezolvare(n, a):
p = u = -1 # poziția de început și de sfârșit a secvenței maxime
max_lungime = max_suma = 0 # lungimea și suma maximă găsite până acum

# parcurgem șirul și căutăm secvența maximă
lungime_secventa = suma_elementelor = 1
for i in range(1, n):
if a[i] % 2 == a[i-1] % 2:
lungime_secventa = 1
suma_elementelor = a[i]
else:
lungime_secventa += 1
suma_elementelor += a[i]
if lungime_secventa > max_lungime or (lungime_secventa == max_lungime and suma_elementelor > max_suma):
max_lungime = lungime_secventa
max_suma = suma_elementelor
p = i - lungime_secventa + 1
u = i

return p, u

def validare(p, u):
with open("secventa.out", "w") as f:
if p == -1:
f.write("-1\n")
else:
f.write(str(p+1) + " " + str(u+1) + "\n")

if __name__ == "__main__":
n, a = citire()
p, u = rezolvare(n, a)
validare(p, u)

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru rezolvarea acestei probleme, vom parcurge şirul dat şi vom folosi două variabile: lungimea_secvenţei pentru a memora lungimea secvenţei curente, şi suma_elementelor pentru a memora suma elementelor din secvenţa curentă. De asemenea, vom mai folosi două variabile: max_lungime pentru a memora lungimea maximă găsită până acum, şi max_suma pentru a memora suma maximă găsită până acum, precum şi două variabile: p pentru a memora poziţia de început a secvenţei maxime şi u pentru a memora poziţia de sfârşit a secvenţei maxime.

În timpul parcurgerii şirului, vom actualiza lungimea_secvenţei şi suma_elementelor pentru fiecare secvenţă găsită, şi vom compara cu valorile maxime găsite până acum, actualizându-le în caz că avem o secvenţă nouă mai bună.

După parcurgerea întregului şir, vom afişa valorile p şi u, adică poziţiile de început şi sfârşit ale secvenţei maxime.