0297 - SecvSumMax - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-14T22:06:23Z

Date de ieșire

← Older revision		Revision as of 22:06, 14 May 2023
Line 10:		Line 10:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire secvsummax.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~~ ''' numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''' fișierul de ieșire secvsummax.out va conține''' numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate''', 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 ==

Flaviu at 21:17, 14 May 2023

2023-05-14T21:17:20Z

← Older revision		Revision as of 21:17, 14 May 2023
Line 29:		Line 29:
	: 4 8		: 4 8

	== Exemplu ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: secvsummax.out		: secvsummax.out
Line 35:		Line 35:
	: -1 2 3 -10 2 8 5 8 4		: -1 2 3 -10 2 8 5 8 4
	; Ieșire		; Ieșire
	~~: secvsummax.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 44:		Line 43:
	# 0297 - SecvSumMax		# 0297 - SecvSumMax

	def ~~citire~~():		def validate_input(n, nums):
	~~try:~~		if not (1 <= n <= 100000):
	n = ~~int(input()~~)		return False
	~~a = []~~		if len(nums) != n:
	~~for i in range~~(n):		return False
	~~a.extend(list(map(int, input().split())))~~		if all(num <= 0 for num in nums):
	return a		return False
	~~except~~:		return True
	~~print("Datele nu corespund restricțiilor impuse.")~~
	return []

	def ~~secvsummax~~(a):		def find_max_subsequence(n, nums):
	~~max_sum = a[0]~~		if not validate_input(n, nums):
			return "Datele nu corespund restricțiilor impuse."

	start, end = 0, 0		start, end = 0, 0
	~~curr_sum~~ = a[0]		max_sum = 0
	~~curr_start~~ = 0		current_sum = 0
	for i in range(~~1, len(a)~~):
	~~if curr_sum < 0:~~		for i in range(n):
	~~curr_sum~~ = a[i]		current_sum += nums[i]
	~~curr_start~~ = i		if current_sum > max_sum:
	~~else:~~		max_sum = current_sum
	~~curr_sum +~~= a[i]		end = i
	if ~~curr_sum > max_sum or (curr_sum == max_sum and i - curr_start~~ < ~~end - start)~~:		if current_sum < 0:
	~~max_sum~~ = ~~curr_sum~~		current_sum = 0
	start~~, end~~ = ~~curr_start,~~ i		start = i + 1
	return start+1, end+1
			return f"{start + 1} {end + 1}"

	~~def validare(a, start, end):~~
	~~return sum(a[start-1:end]) == max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))~~

	if __name__ == "__main__":		if __name__ == "__main__":
	a = ~~citire~~()		file_name = "secvsummax.in"
	~~if a~~:		with open(file_name, "r") as file:
	~~start, end~~ = ~~secvsummax~~(a)		n = int(file.readline())
	~~if validare~~(~~a, start, end~~):		nums = []
	~~print~~(~~"Datele sunt introduse corect~~.")		for _ in range(n):
	~~print~~(~~start, end~~)		nums.extend(map(int, file.readline().split()))
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse."~~)
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse."~~)

			result = find_max_subsequence(n, nums)
			print(result)

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru a rezolva această problemă putem folosi algoritmul Kadane~~, ~~care constă~~ în ~~a parcurge șirul și a calcula suma maximă a unei subsecvențe care~~ se ~~termină la fiecare element~~. ~~De asemenea~~, ~~menținem și pozițiile de început și sfârșit ale acestei subsecvențe~~. ~~La fiecare pas~~, dacă ~~suma calculată este~~ mai mare decât ~~suma maximă anterioră~~, ~~actualizăm pozițiile~~ de ~~început~~ și ~~sfârșit ale subsecvenței~~ cu suma maximă. ~~La final, returnăm aceste poziții.~~		validate_input(n, nums): Această funcție primește un număr n și o listă nums și validează datele de intrare în conformitate cu restricțiile impuse. Verificările efectuate sunt:
	Funcția ~~citire citește datele~~ de intrare, ~~formate din n următoarele linii, fiecare conținând o valoare din șir. Lista a este construită prin extinderea sub-listelor formate din aceste valori~~.
			Verifică dacă n se află în intervalul [1, 100000]. Dacă nu se îndeplinește această condiție, funcția returnează False, semnalând că datele nu sunt valide.
			Verifică dacă lungimea listei nums este egală cu n. Dacă lungimea nu este corectă, funcția returnează False.
			Verifică dacă toate numerele din lista nums sunt mai mici sau egale cu 0. Dacă există cel puțin un număr mai mare decât 0, funcția returnează False.
			Dacă toate aceste verificări sunt îndeplinite, funcția returnează True, semnalând că datele de intrare sunt valide.
			find_max_subsequence(n, nums): Această funcție primește un număr n și o listă nums și aplică algoritmul pentru a găsi secvența de elemente cu suma maximă. Funcția începe prin apelarea funcției validate_input pentru a verifica validitatea datelor de intrare. Dacă datele nu sunt valide, funcția returnează mesajul "Datele nu corespund restricțiilor impuse."

	~~Funcția secvsummax primește~~ lista a și ~~returnează pozițiile de început~~ și ~~sfârșit ale subsecvenței cu suma maximă~~, ~~conform algoritmului Kadane~~.		Dacă datele sunt valide, funcția inițializează variabilele start, end, max_sum și current_sum cu valorile inițiale 0. Apoi, parcurge lista nums folosind un buclă for și adaugă fiecare element la suma curentă current_sum. Dacă current_sum devine mai mare decât max_sum, actualizează max_sum cu current_sum și actualizează end la poziția curentă. Dacă current_sum devine mai mică decât 0, resetează-o la 0 și actualizează start la poziția curentă + 1.

	~~Funcția validare primește lista~~ a ~~și pozițiile~~ de ~~început și sfârșit ale unei subsecvențe și returnează True dacă această subsecvență are suma maximă și False în caz contrar~~.		La finalul buclei, funcția returnează rezultatul sub forma unui șir format din start + 1 și end + 1. Adăugarea valorii 1 este necesară pentru a respecta numerotarea elementelor de la 1 la n.

	~~În funcția principală, se apelează funcția~~ citire~~, apoi se determină subsecvența cu suma maximă cu ajutorul~~ funcției ~~secvsummax~~. ~~Dacă această subsecvență este validă~~, se ~~afișează pozițiile~~ de ~~început și sfârșit, altfel se afișează~~ "~~Eroare~~".		__main__: Această secțiune verifică dacă scriptul este executat direct (nu importat ca modul) și conține codul de citire a fișierului de intrare și apelarea funcției find_max_subsequence. Mai întâi, se deschide fișierul de intrare secvsummax.in în modul "r" (citire). Se citește prima linie pentru a obține valoarea lui n, iar apoi se citesc următoarele `n

Flaviu at 07:54, 3 May 2023

2023-05-03T07:54:18Z

← Older revision		Revision as of 07:54, 3 May 2023
Line 12:		Line 12:
	Fișierul de ieșire secvsummax.out va conține:		Fișierul de ieșire secvsummax.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 ''' numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate''', 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 19:		Line 19:
	* dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă		* dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
	* șirul va conține cel puțin un element pozitiv		* șirul va conține cel puțin un element pozitiv
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: secvsummax.out
	: 10		: 10
	: -4 1 -5 1 4 -2 2 3 -4 4		: -4 1 -5 1 4 -2 2 3 -4 4
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: secvsummax.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 4 8		: 4 8

			== Exemplu ==
			; Intrare
			: secvsummax.out
			: 67
			: -1 2 3 -10 2 8 5 8 4
			; Ieșire
			: secvsummax.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:32, 28 April 2023

2023-04-28T14:32:24Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire secvsummax.out va conține pe ~~prima linie numerele p și u~~, ~~separate printr-~~un ~~spațiu~~, reprezentând ~~poziția de început și de sfârșit a secvenței determinate~~.		Fișierul de ieșire secvsummax.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 22:		Line 24:
	: -4 1 -5 1 4 -2 2 3 -4 4		: -4 1 -5 1 4 -2 2 3 -4 4
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 4 8		: 4 8

Line 30:		Line 34:

	def citire():		def citire():
	n = int(input())		try:
	a = []		n = int(input())
	for i in range(n):		a = []
	a.extend(list(map(int, input().split())))		for i in range(n):
	return a		a.extend(list(map(int, input().split())))
			return a
			except:
			print("Datele nu corespund restricțiilor impuse.")
			return []

	def secvsummax(a):		def secvsummax(a):
Line 57:		Line 65:
	if __name__ == "__main__":		if __name__ == "__main__":
	a = citire()		a = citire()
	start, end = secvsummax(a)		if a:
	if validare(a, start, end):		start, end = secvsummax(a)
	print(start, end)		if validare(a, start, end):
			print("Datele sunt introduse corect.")
			print(start, end)
			else:
			print("Datele nu corespund restricțiilor impuse.")
	else:		else:
	print("~~Eroare~~")		print("Datele nu corespund restricțiilor impuse.")

Flaviu at 06:52, 18 April 2023

2023-04-18T06:52:48Z

← Older revision		Revision as of 06:52, 18 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/~~304~~/~~secvente~~ 0297 - SecvSumMax]		Sursa: [https://www.pbinfo.ro/probleme/297/secvsummax 0297 - SecvSumMax]
	----		----
	== Cerinţa ==		== Cerinţa ==

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 0297 - SecvSumMax] ---- == Cerinţa == Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă. == Date de intrare == Fișierul de intrare secvsummax.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 secvsummax.out va conține pe prima linie numerele p și...

2023-04-18T06:51:47Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 0297 - SecvSumMax] ---- == Cerinţa == Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă. == Date de intrare == Fișierul de intrare secvsummax.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 secvsummax.out va conține pe prima linie numerele p și...

New page

Sursa: [https://www.pbinfo.ro/probleme/304/secvente 0297 - SecvSumMax]
----
== Cerinţa ==
Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă.

== Date de intrare ==
Fișierul de intrare secvsummax.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 secvsummax.out va conține pe prima linie numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
* elementele șirului vor avea cel mult 4 cifre și sunt numerotate de la 1 la n
* dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
* șirul va conține cel puțin un element pozitiv
== Exemplu ==
; Intrare
: 10
: -4 1 -5 1 4 -2 2 3 -4 4
; Ieșire
: 4 8

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0297 - SecvSumMax

def citire():
n = int(input())
a = []
for i in range(n):
a.extend(list(map(int, input().split())))
return a

def secvsummax(a):
max_sum = a[0]
start, end = 0, 0
curr_sum = a[0]
curr_start = 0
for i in range(1, len(a)):
if curr_sum < 0:
curr_sum = a[i]
curr_start = i
else:
curr_sum += a[i]
if curr_sum > max_sum or (curr_sum == max_sum and i - curr_start < end - start):
max_sum = curr_sum
start, end = curr_start, i
return start+1, end+1

def validare(a, start, end):
return sum(a[start-1:end]) == max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))

if __name__ == "__main__":
a = citire()
start, end = secvsummax(a)
if validare(a, start, end):
print(start, end)
else:
print("Eroare")

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă putem folosi algoritmul Kadane, care constă în a parcurge șirul și a calcula suma maximă a unei subsecvențe care se termină la fiecare element. De asemenea, menținem și pozițiile de început și sfârșit ale acestei subsecvențe. La fiecare pas, dacă suma calculată este mai mare decât suma maximă anterioră, actualizăm pozițiile de început și sfârșit ale subsecvenței cu suma maximă. La final, returnăm aceste poziții.
Funcția citire citește datele de intrare, formate din n următoarele linii, fiecare conținând o valoare din șir. Lista a este construită prin extinderea sub-listelor formate din aceste valori.

Funcția secvsummax primește lista a și returnează pozițiile de început și sfârșit ale subsecvenței cu suma maximă, conform algoritmului Kadane.

Funcția validare primește lista a și pozițiile de început și sfârșit ale unei subsecvențe și returnează True dacă această subsecvență are suma maximă și False în caz contrar.

În funcția principală, se apelează funcția citire, apoi se determină subsecvența cu suma maximă cu ajutorul funcției secvsummax. Dacă această subsecvență este validă, se afișează pozițiile de început și sfârșit, altfel se afișează "Eroare".