1804 - ursulet - Revision history

Monica Dragos at 22:39, 14 May 2023

2023-05-14T22:39:52Z

← Older revision		Revision as of 22:39, 14 May 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/1804/ursulet 1804 - ursulet]		Sursa: [https://www.pbinfo.ro/probleme/1804/ursulet 1804 - ursulet]
	----		----
	Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.

	== Cerinţa ==		== Cerinţa ==
			Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.
	Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.		Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.

Line 12:		Line 13:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire ursulet.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 '''~~pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță''', 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 ursulet.out va conține pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

Flaviu at 21:56, 14 May 2023

2023-05-14T21:56:47Z

← Older revision		Revision as of 21:56, 14 May 2023
Line 27:		Line 27:
	: -5 0 3 1 -4 2		: -5 0 3 1 -4 2
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: ursulet.out		: ursulet.out
	~~: Datele sunt introduse correct.~~
	: 4		: 4
	: 2 4		: 2 4
Line 38:		Line 38:
	: 0.23 0 1 1 4.76 -1 -2		: 0.23 0 1 1 4.76 -1 -2
	; Ieșire		; Ieșire
	~~: ursulet.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 47:		Line 46:
	# 1804 - ursulet		# 1804 - ursulet

	def ~~read_input~~():		def validare_altitudini(altitudini):
	~~n = int(input())~~		for altitudine in altitudini:
	~~altitudes = list(map(int, input().split()))~~		if not (-1000 <= altitudine <= 1000):
	~~return altitudes~~		return False
			return True
	~~def find_maximum_subarray(altitudes):~~
	~~max_sum = float('-inf')~~
	~~current_sum = 0~~
	~~start_index = 0~~
	~~end_index = -1~~
	~~current_start_index = 0~~

	for i in ~~range(len(altitudes))~~:
	~~current_sum += altitudes[i]~~

	if ~~current_sum > max_sum:~~
	~~max_sum~~ = ~~current_sum~~
	~~start_index~~ = ~~current_start_index~~
	~~end_index = i~~

	~~if current_sum < 0~~:
	~~current_sum = 0~~
	~~current_start_index = i + 1~~

	~~return max_sum, start_index, end_index~~

	def ~~write_output~~(~~result~~):		def obos_max(altitudini):
	~~max_sum, start_index, end_index~~ = ~~result~~		suma_oboseala = 0
	~~with open~~(~~'ursulet.out', 'w'~~) ~~as f~~:		obos_maxim = 0
	~~f.write(str(max_sum)~~ + ~~'\n')~~		inceput = 0
	~~f.write(str(start_index~~ + 1~~) + ' ' + str~~(~~end_index~~ + 1) + ~~'\n'~~)		sfarsit = 0
			index = 0

			for i in range(len(altitudini)):
			suma_oboseala += altitudini[i]

			if suma_oboseala < 0:
			suma_oboseala = 0
			index = i + 1
			elif suma_oboseala > obos_maxim:
			obos_maxim = suma_oboseala
			inceput = index
			sfarsit = i

			return (obos_maxim, inceput + 1, sfarsit + 1)

	~~def validate_output(expected_output, actual_output):~~
	~~with open(expected_output, 'r') as f:~~
	~~expected_values = f.readlines()~~
	~~actual_values = actual_output.strip().split('\n')~~
	~~return expected_values == actual_values~~

	if __name__ == '__main__':		if __name__ == '__main__':
	~~altitudes~~ = ~~read_input~~()		with open('ursulet.in', 'r') as f:
	~~result~~ = ~~find_maximum_subarray~~(~~altitudes~~)		n = int(f.readline())
	~~write_output~~(~~result~~)		altitudini = list(map(int, f.readline().split()))

	if ~~validate_output~~(~~'ursulet~~.~~ok', 'ursulet.out'~~):		if not validare_altitudini(altitudini):
			print("Datele nu corespund restricțiilor impuse.")
			else:
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	~~else:~~		oboseala_max, inceput, sfarsit = obos_max(altitudini)
	~~print~~(~~"Datele nu corespund restricțiilor impuse~~.")		with open('ursulet.out', 'w') as f:
			f.write(str(oboseala_max) + '\n')
			f.write(str(inceput) + ' ' + str(sfarsit) + '\n')

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Acest cod definește o funcție `read_input~~()~~` care citește un număr întreg `n` de la intrare și o listă~~ de numere întregi ~~`altitudes` separate prin spații. Lista de altitudini reprezintă altitudinile succesive ale unui traseu~~ și ~~reprezintă datele de intrare pentru a afla cea mai mare sumă a unei subsecvențe din traseu. Funcția returnează lista de altitudini.~~		În funcția validare_altitudini(altitudini) se verifică dacă toate valorile altitudinilor îndeplinesc condițiile impuse de problema (sunt numere întregi între -1000 și 1000). Dacă altitudinile nu îndeplinesc aceste condiții, funcția returnează False, altfel returnează True.

	~~Funcția `find_maximum_subarray(altitudes~~)` primește lista de altitudini și găsește subsecvența cu cea mai mare sumă. Pentru a face acest lucru, se utilizează o abordare de tip "divide and conquer" care parcurge lista și calculează suma subsecvențelor succesive. Se actualizează maximumul și indicii începutului și sfârșitului subsecvenței cu cea mai mare sumă de fiecare dată când se găsește o sumă mai mare decât maximul actual. Dacă ~~suma curentă scade sub zero~~, ~~subsecvența curentă este abandonată și se începe o nouă subsecvență la poziția următoare. Funcția~~ returnează ~~o tuplă care conține suma maximă~~, ~~indicele de început și indicele de sfârșit ai subsecvenței cu suma maximă~~.

	~~Funcția `write_output~~(~~result~~)~~` primește rezultatul găsit~~ de ~~`find_maximum_subarray~~(~~altitudes~~)` și ~~îl scrie într-un fișier numit 'ursulet~~.~~out'~~, ~~pe două linii separate~~. ~~Prima linie conține~~ suma maximă ~~a subsecvenței~~, ~~iar a doua linie conține indicii~~ de început și sfârșit ~~ai subsecvenței cu suma~~ maximă~~, separate printr-un spațiu~~.		În funcția obos_max(altitudini) se parcurg altitudinile în ordine și se calculează obosiala maximă acumulată de Ursuleț pe o porțiune de zone consecutive. Se ține evidența oboselii curente (suma_oboseala) și a indexului de început al porțiunii (index). Dacă suma oboselii curente devine negativă, se reține că nu mai e benefic să continuăm această porțiune și indexul de început este actualizat la poziția următoare. Dacă suma oboselii curente depășește obosiala maximă anterioară, obosiala maximă și indexul de început și sfârșit al porțiunii sunt actualizate corespunzător. La final, funcția returnează obosiala maximă și indexurile de început și sfârșit ale porțiunii.

	În ~~funcția `main`, lista~~ de ~~altitudini este citită~~ cu ~~ajutorul `read_input~~()`, ~~apoi~~ funcția ~~`find_maximum_subarray~~(~~altitudes~~)~~` este apelată pentru a găsi subsecvența cu suma~~ maximă. ~~Rezultatul este scris într-~~un ~~fișier cu ajutorul `write_output(result)`~~.		În blocul if __name__ == '__main__': se citesc datele de intrare din fișierul ursulet.in. Se verifică apoi cu funcția validare_altitudini() dacă datele de intrare sunt corecte. Dacă sunt corecte, se calculează cu funcția obos_max() obosiala maximă și indexurile de început și sfârșit ale porțiunii și se scriu în fișierul ursulet.out. Dacă datele de intrare nu sunt corecte, se afișează un mesaj corespunzător.

Flaviu at 08:11, 3 May 2023

2023-05-03T08:11:20Z

← Older revision		Revision as of 08:11, 3 May 2023
Line 14:		Line 14:
	Fișierul de ieșire ursulet.out va conține:		Fișierul de ieșire ursulet.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 '''pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


Line 21:		Line 21:
	* -1000 ≤ a ≤ 1000, a fiind altitudinea unei zone		* -1000 ≤ a ≤ 1000, a fiind altitudinea unei zone
	* Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.ă cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător		* Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.ă cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: ursulet.in
	: 6		: 6
	: -5 0 3 1 -4 2		: -5 0 3 1 -4 2
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: ursulet.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 4		: 4
	: 2 4		: 2 4

			== Exemplu 2 ==
			; Intrare
			: ursulet.in
			: 6
			: 0.23 0 1 1 4.76 -1 -2
			; Ieșire
			: ursulet.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:58, 28 April 2023

2023-04-28T14:58:02Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ursulet.out va conține pe ~~prima linie~~ un ~~număr întreg ce semnifică oboseală maximă acumulată de ursuleţ~~ pe ~~o porţiune de zone consecutive~~. ~~Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță~~.		Fișierul de ieșire ursulet.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 23:		Line 26:
	: -5 0 3 1 -4 2		: -5 0 3 1 -4 2
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 4		: 4
	: 2 4		: 2 4
Line 62:		Line 67:
	f.write(str(max_sum) + '\n')		f.write(str(max_sum) + '\n')
	f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')		f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')

			def validate_output(expected_output, actual_output):
			with open(expected_output, 'r') as f:
			expected_values = f.readlines()
			actual_values = actual_output.strip().split('\n')
			return expected_values == actual_values

	if __name__ == '__main__':		if __name__ == '__main__':
Line 67:		Line 78:
	result = find_maximum_subarray(altitudes)		result = find_maximum_subarray(altitudes)
	write_output(result)		write_output(result)

			if validate_output('ursulet.ok', 'ursulet.out'):
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Pentru a ~~rezolva această problemă~~, ~~putem utiliza~~ o ~~metodă numită~~ "~~maximum subarray problem~~", care ~~constă în găsirea~~ subsecvenței ~~continue a unui șir dat, care are~~ cea mai mare sumă. ~~Putem utiliza~~ o ~~variantă~~ a ~~algoritmului Kadane~~, ~~care funcționează în timp liniar~~.		Acest cod definește o funcție `read_input()` care citește un număr întreg `n` de la intrare și o listă de numere întregi `altitudes` separate prin spații. Lista de altitudini reprezintă altitudinile succesive ale unui traseu și reprezintă datele de intrare pentru a afla cea mai mare sumă a unei subsecvențe din traseu. Funcția returnează lista de altitudini.

			Funcția `find_maximum_subarray(altitudes)` primește lista de altitudini și găsește subsecvența cu cea mai mare sumă. Pentru a face acest lucru, se utilizează o abordare de tip "divide and conquer" care parcurge lista și calculează suma subsecvențelor succesive. Se actualizează maximumul și indicii începutului și sfârșitului subsecvenței cu cea mai mare sumă de fiecare dată când se găsește o sumă mai mare decât maximul actual. Dacă suma curentă scade sub zero, subsecvența curentă este abandonată și se începe o nouă subsecvență la poziția următoare. Funcția returnează o tuplă care conține suma maximă, indicele de început și indicele de sfârșit ai subsecvenței cu suma maximă.

			Funcția `write_output(result)` primește rezultatul găsit de `find_maximum_subarray(altitudes)` și îl scrie într-un fișier numit 'ursulet.out', pe două linii separate. Prima linie conține suma maximă a subsecvenței, iar a doua linie conține indicii de început și sfârșit ai subsecvenței cu suma maximă, separate printr-un spațiu.

			În funcția `main`, lista de altitudini este citită cu ajutorul `read_input()`, apoi funcția `find_maximum_subarray(altitudes)` este apelată pentru a găsi subsecvența cu suma maximă. Rezultatul este scris într-un fișier cu ajutorul `write_output(result)`.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1804/ursulet 1804 - ursulet] ---- Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transpor...

2023-04-18T07:21:33Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1804/ursulet 1804 - ursulet] ---- Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transpor...

New page

Sursa: [https://www.pbinfo.ro/probleme/1804/ursulet 1804 - ursulet]
----
Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.

== Cerinţa ==
Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.

== Date de intrare ==
Fișierul de intrare ursulet.in conține pe prima linie numărul N, ce semnifică numărul de zone traversate de ursuleţ. Pe linia următoare se află N numere întregi, altitudinile zonelor.

== Date de ieșire ==
Fișierul de ieșire ursulet.out va conține pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000
* -1000 ≤ a ≤ 1000, a fiind altitudinea unei zone
* Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.ă cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
== Exemplu ==
; Intrare
: 6
: -5 0 3 1 -4 2
; Ieșire
: 4
: 2 4

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 1804 - ursulet

def read_input():
n = int(input())
altitudes = list(map(int, input().split()))
return altitudes

def find_maximum_subarray(altitudes):
max_sum = float('-inf')
current_sum = 0
start_index = 0
end_index = -1
current_start_index = 0

for i in range(len(altitudes)):
current_sum += altitudes[i]

if current_sum > max_sum:
max_sum = current_sum
start_index = current_start_index
end_index = i

if current_sum < 0:
current_sum = 0
current_start_index = i + 1

return max_sum, start_index, end_index

def write_output(result):
max_sum, start_index, end_index = result
with open('ursulet.out', 'w') as f:
f.write(str(max_sum) + '\n')
f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')

if __name__ == '__main__':
altitudes = read_input()
result = find_maximum_subarray(altitudes)
write_output(result)

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem utiliza o metodă numită "maximum subarray problem", care constă în găsirea subsecvenței continue a unui șir dat, care are cea mai mare sumă. Putem utiliza o variantă a algoritmului Kadane, care funcționează în timp liniar.