2921 - SumeSecv1 - Revision history

Flaviu at 20:50, 14 May 2023

2023-05-14T20:50:28Z

← Older revision		Revision as of 20:50, 14 May 2023
Line 40:		Line 40:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: 14~~
	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 2921 - SumeSecv1		# 2921 - SumeSecv1
	def ~~suma_maxima~~(n, nr, m, ~~perechi~~):		def validate_input(n, arr, m, pairs):
	~~# Verificăm restricțiile impuse~~		if not(1 <= n <= 100000 and 1 <= m <= 500000 and len(arr) == n and len(pairs) == m):
	if n < 1 ~~or n > 100000 or~~ m < ~~1 or~~ m ~~> 500000~~:		print("Datele nu corespund restricțiilor impuse.")
	return "Datele nu corespund ~~restrictiilor~~ impuse."		return False
	for i, j in ~~perechi~~:		for num in arr:
	if i < ~~1 or i > n or~~ j < ~~1 or j >~~ n:		if abs(num) > 10**9:
	~~return~~ "Datele nu corespund ~~restrictiilor~~ impuse."		print("Datele nu corespund restricțiilor impuse.")
			return False
	~~# Calculăm suma maximă~~		for i, j in pairs:
	~~s_max = 0~~		if not (1 <= i <= j <= n):
	~~s_curenta = 0~~		print("Datele nu corespund restricțiilor impuse.")
	~~for i in range~~(n):		return False
	~~s_curenta += nr[i]~~		print("Datele sunt introduse corect.")
	if ~~s_curenta < 0~~:		return True
	~~s_curenta = 0~~
	~~elif s_curenta > s_max:~~
	~~s_max = s_curenta~~		def find_max_sum(n, arr, m, pairs):
			if not validate_input(n, arr, m, pairs):
	for i, j in ~~perechi~~:		return
	s = sum(nr[i-1:j])
	if s > ~~s_max~~:		max_sum = float('-inf')
	~~s_max~~ = s		for i, j in pairs:
			curr_sum = sum(arr[i-1:j])
	~~return s_max~~		if curr_sum > max_sum:
			max_sum = curr_sum

			print(max_sum)


	if __name__ == "__main__":		if __name__ == "__main__":
	~~# Citim datele de intrare~~
	n = int(input())		n = int(input())
	nr = list(map(int, input().split()))		arr = list(map(int, input().split()))
	m = int(input())		m = int(input())
	~~perechi~~ = [~~tuple~~(map(int, input().split())) ~~for _ in range(m~~)]		pairs = []
			for _ in range(m):
	~~# Apelăm funcția și afișăm rezultatul~~		i, j = map(int, input().split())
	~~rezultat = suma_maxima~~(n, nr, m, ~~perechi)~~		pairs.append((i, j))
	~~if isinstance(rezultat, str):~~		find_max_sum(n, arr, m, pairs)
	~~print(rezultat~~)
	~~else:~~
	~~print("Datele sunt introduse corect.")~~
	~~print(rezultat)~~

	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~citeste_date(): această~~ funcție ~~are rolul~~ de ~~a citi datele~~ de ~~la tastatură~~ și ~~de a returna valorile citite sub forma a două liste. Mai întâi se citește numărul n și apoi elementele șirului a, apoi numărul~~ de perechi ~~m și apoi perechile~~ de indici i și j. ~~Valorile citite sub forma de liste~~ sunt ~~returnate într-un tuplu de forma (a, indici)~~.		Funcția `validate_input` este o funcție care primește ca parametrii dimensiunile listei de numere întregi, lista de numere întregi și lista de perechi de indici, verifica dacă datele introduse corespund restricțiilor impuse și afișează un mesaj corespunzător. Aceasta returnează `True` dacă datele sunt corecte și `False` în caz contrar.
	Funcția ~~suma_maxima(a, indici): această funcție~~ primește ca ~~argumente lista a cu elementele șirului~~ și ~~lista indici cu perechile de indici~~ și ~~are rolul de a calcula~~ suma maximă dintre toate secvențele ~~posibile determinate~~ de perechile de indici. ~~Pentru fiecare pereche~~ de ~~indici (i~~, ~~j), se calculează suma elementelor din secvența determinată de acești indici, iar apoi se determină suma maximă dintre toate aceste sume. Funcția returnează această suma maximă~~.
			Funcția `find_max_sum` primește aceleași parametrii ca și `validate_input`. Verifică dacă datele sunt introduse corect prin apelarea funcției `validate_input` și returnează `None` dacă datele nu sunt corecte. În caz contrar, calculează și afișează suma maximă dintre toate secvențele date de perechile de indici.

			Funcția `main` citește datele de intrare, apelează funcția `find_max_sum` și afișează rezultatul.

Flaviu at 22:19, 13 May 2023

2023-05-13T22:19:11Z

← Older revision		Revision as of 22:19, 13 May 2023
Line 25:		Line 25:
	: 4 2		: 4 2
	: 2 5		: 2 5

	; Ieșire		; Ieșire
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 10		: 10

	== Exemplu 1 ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: 5 ~~1 2~~		: 5
	: 7 9 -6 1 -8		: 7 9 -6 1 -8
	: ~~3 3 3~~		: 2
	: 1 3		: 1 5
	: 4 2 3		: 2 4 3
	~~: 2 5 4~~
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: ~~2 3 4~~		: 14

	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 2921 - SumeSecv1		# 2921 - SumeSecv1
	def ~~citire~~():		def suma_maxima(n, nr, m, perechi):
			# Verificăm restricțiile impuse
			if n < 1 or n > 100000 or m < 1 or m > 500000:
			return "Datele nu corespund restrictiilor impuse."
			for i, j in perechi:
			if i < 1 or i > n or j < 1 or j > n:
			return "Datele nu corespund restrictiilor impuse."

			# Calculăm suma maximă
			s_max = 0
			s_curenta = 0
			for i in range(n):
			s_curenta += nr[i]
			if s_curenta < 0:
			s_curenta = 0
			elif s_curenta > s_max:
			s_max = s_curenta

			for i, j in perechi:
			s = sum(nr[i-1:j])
			if s > s_max:
			s_max = s

			return s_max

			if __name__ == "__main__":
			# Citim datele de intrare
	n = int(input())		n = int(input())
	a = list(map(int, input().split()))		nr = list(map(int, input().split()))
	m = int(input())		m = int(input())
	perechi = []		perechi = [tuple(map(int, input().split())) for _ in range(m)]
	~~for i in range(m):~~
	~~perechi.append(~~tuple(map(int, input().split())))		# Apelăm funcția și afișăm rezultatul
	~~return n, a, m, perechi~~		rezultat = suma_maxima(n, nr, m, perechi)
			if isinstance(rezultat, str):
			print(rezultat)
	~~def calc_suma_max~~(n, a, m, perechi):		else:
	~~suma_maxima = 0~~
	~~for i, j in perechi:~~
	if ~~i >= j or i < 1 or j > n:~~
	~~print~~(~~"Datele nu corespund restricțiilor impuse.")~~
	~~return~~
	~~suma_curenta = 0~~
	~~suma_max_subsecventa = float('-inf')~~
	~~for k in range(i-1~~, j):
	~~suma_curenta += a[k]~~
	~~if suma_curenta > suma_max_subsecventa:~~
	~~suma_max_subsecventa = suma_curenta~~
	~~if suma_curenta < 0:~~
	~~suma_curenta = 0~~
	print(~~suma_max_subsecventa)~~


	~~if __name__ == '__main__':~~
	~~n, a, m, perechi = citire(~~)
	~~if 1 <= n <= 100 and all(0 <= x < 1000 for x in a) and 1 <= m <= 100~~:
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	~~calc_suma_max(n, a, m, perechi)~~		print(rezultat)
	~~else:~~
	print(~~"Datele nu corespund restricțiilor impuse."~~)

	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~citire~~ citește ~~datele~~ de ~~intrare~~ și ~~le returnează~~ într-~~o tuplă~~.		Funcția citeste_date(): această funcție are rolul de a citi datele de la tastatură și de a returna valorile citite sub forma a două liste. Mai întâi se citește numărul n și apoi elementele șirului a, apoi numărul de perechi m și apoi perechile de indici i și j. Valorile citite sub forma de liste sunt returnate într-un tuplu de forma (a, indici).
	Funcția ~~calc_suma_max calculează~~ suma maximă ~~a unei subsecvențe pentru~~ fiecare pereche de indici ~~și returnează~~ suma maximă dintre toate ~~sumele calculate~~.		Funcția suma_maxima(a, indici): această funcție primește ca argumente lista a cu elementele șirului și lista indici cu perechile de indici și are rolul de a calcula suma maximă dintre toate secvențele posibile determinate de perechile de indici. Pentru fiecare pereche de indici (i, j), se calculează suma elementelor din secvența determinată de acești indici, iar apoi se determină suma maximă dintre toate aceste sume. Funcția returnează această suma maximă.
	Funcția ~~validare verifică dacă~~ suma maximă ~~se încadrează în limitele impuse de enunț.~~
	~~În funcția main, apelăm funcțiile citire, calc_suma_max, print și validare în ordinea specificată în enunț~~.

Flaviu at 07:45, 3 May 2023

2023-05-03T07:45:36Z

← Older revision		Revision as of 07:45, 3 May 2023
Line 9:		Line 9:
	== Date de ieșire ==		== Date de ieșire ==
	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 '''numărul S, reprezentând suma maximă 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 ==
Line 17:		Line 17:
	cele n elemente ale șirului vor avea cel mult nouă cifre.		cele n elemente ale șirului vor avea cel mult nouă cifre.

	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 5		: 5
Line 26:		Line 26:
	: 2 5		: 2 5
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 10		: 10

			== Exemplu 1 ==
			; Intrare
			: 5 1 2
			: 7 9 -6 1 -8
			: 3 3 3
			: 1 3
			: 4 2 3
			: 2 5 4
			; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: 2 3 4

	== Rezolvare ==		== Rezolvare ==

Flaviu at 18:44, 27 April 2023

2023-04-27T18:44:17Z

← Older revision		Revision as of 18:44, 27 April 2023
Line 8:		Line 8:

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ~~ecran~~ numărul S, reprezentând ~~suma maximă determinată~~.		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 25:		Line 26:
	: 2 5		: 2 5
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 10		: 10

Line 44:		Line 47:
	suma_maxima = 0		suma_maxima = 0
	for i, j in perechi:		for i, j in perechi:
			if i >= j or i < 1 or j > n:
			print("Datele nu corespund restricțiilor impuse.")
			return
	suma_curenta = 0		suma_curenta = 0
	suma_max_subsecventa = float('-inf')		suma_max_subsecventa = float('-inf')
Line 52:		Line 58:
	if suma_curenta < 0:		if suma_curenta < 0:
	suma_curenta = 0		suma_curenta = 0
	if suma_max_subsecventa ~~> suma_maxima:~~		print(suma_max_subsecventa)
	~~suma_maxima = suma_max_subsecventa~~
	~~return suma_maxima~~


	~~def validare(suma_maxima):~~
	~~assert suma_maxima >= -9000000000 and suma_maxima <= 9000000000~~


	if __name__ == '__main__':		if __name__ == '__main__':
	n, a, m, perechi = citire()		n, a, m, perechi = citire()
	~~suma_maxima~~ = calc_suma_max(n, a, m, perechi)		if 1 <= n <= 100 and all(0 <= x < 1000 for x in a) and 1 <= m <= 100:
	print(~~suma_maxima)~~		print("Datele sunt introduse corect.")
	~~validare(suma_maxima~~)		calc_suma_max(n, a, m, perechi)
			else:
			print("Datele nu corespund restricțiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția citire citește datele de intrare și le returnează într-o tuplă.		Funcția citire citește datele de intrare și le returnează într-o tuplă.

Flaviu: Pagină nouă: Sursa: [https://https://www.pbinfo.ro/probleme/2921/sumesecv1 2921 - SumeSecv1] ---- == Cerinţa == Se dă un șir cu n elemente numere întregi, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j. == Date...

2023-04-17T20:14:56Z

Pagină nouă: Sursa: [https://https://www.pbinfo.ro/probleme/2921/sumesecv1 2921 - SumeSecv1] ---- == Cerinţa == Se dă un șir cu n elemente numere întregi, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j. == Date...

New page

Sursa: [https://https://www.pbinfo.ro/probleme/2921/sumesecv1 2921 - SumeSecv1]
----
== Cerinţa ==
Se dă un șir cu n elemente numere întregi, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută.
== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j.

== Date de ieșire ==
Programul va afișa pe ecran numărul S, reprezentând suma maximă determinată.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000;
* 1 ≤ m ≤ 500.000;
* 1 ≤ i,j ≤ n;
cele n elemente ale șirului vor avea cel mult nouă cifre.

== Exemplu ==
; Intrare
: 5
: 7 9 -6 1 -8
: 3
: 1 3
: 4 2
: 2 5
; Ieșire
: 10

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2921 - SumeSecv1
def citire():
n = int(input())
a = list(map(int, input().split()))
m = int(input())
perechi = []
for i in range(m):
perechi.append(tuple(map(int, input().split())))
return n, a, m, perechi

def calc_suma_max(n, a, m, perechi):
suma_maxima = 0
for i, j in perechi:
suma_curenta = 0
suma_max_subsecventa = float('-inf')
for k in range(i-1, j):
suma_curenta += a[k]
if suma_curenta > suma_max_subsecventa:
suma_max_subsecventa = suma_curenta
if suma_curenta < 0:
suma_curenta = 0
if suma_max_subsecventa > suma_maxima:
suma_maxima = suma_max_subsecventa
return suma_maxima

def validare(suma_maxima):
assert suma_maxima >= -9000000000 and suma_maxima <= 9000000000

if __name__ == '__main__':
n, a, m, perechi = citire()
suma_maxima = calc_suma_max(n, a, m, perechi)
print(suma_maxima)
validare(suma_maxima)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire citește datele de intrare și le returnează într-o tuplă.
Funcția calc_suma_max calculează suma maximă a unei subsecvențe pentru fiecare pereche de indici și returnează suma maximă dintre toate sumele calculate.
Funcția validare verifică dacă suma maximă se încadrează în limitele impuse de enunț.
În funcția main, apelăm funcțiile citire, calc_suma_max, print și validare în ordinea specificată în enunț.