3846 - KSum2 - Revision history

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

2023-05-14T22:41:04Z

Date de ieșire

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

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire ksum2.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 '''rima~~ linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W''', 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 ksum2.out va conține pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W''', 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 22:01, 14 May 2023

2023-05-14T22:01:44Z

← Older revision		Revision as of 22:01, 14 May 2023
Line 25:		Line 25:
	: 10 12 14		: 10 12 14
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: ksum2.out		: ksum2.out
	~~: Datele sunt introduse correct.~~
	: 3		: 3

Line 36:		Line 36:
	: -0,12 123 0 1 -2 -3 1,23		: -0,12 123 0 1 -2 -3 1,23
	; Ieșire		; Ieșire
	~~: ksum2.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 45:		Line 44:
	# 3846 - KSum2		# 3846 - KSum2

	def ~~read_input~~():		def validate_input(N, K, W, arr):
	~~with open("ksum2.in"~~, ~~"r") as fin~~:		# Verificăm dacă N, K și W respectă restricțiile
	~~n, k, w = map(int, fin.readline().split())~~		if not 1 <= N <= 1000 or not 1 <= K <= N or not K <= W <= N:
	v = ~~list(map(int, fin.readline().split()))~~		return False
	return ~~n, k, w, v~~
			# Verificăm dacă elementele din vector respectă restricțiile
			for x in arr:
			if not -9999 <= x <= 9999:
			return False

			return True

	def ~~solve~~(~~n, k~~, w, v):
	~~max_sum = [0] * n~~		def max_sequence_sum(arr, K, W):
	~~current_sum = 0~~		# Inițializăm variabilele necesare pentru calculul sumei maxime
	~~for i in range(n):~~		max_sum = -float('inf')
	~~current_sum += v[i]~~		cur_sum = 0
	~~if i >~~= k:		start = end = 0
	~~current_sum~~ -~~= v[i - k]~~
	~~if i >= k - 1:~~
	~~max_sum[i] = max~~(~~max_sum[i - 1], current_sum~~)
	~~else:~~
	~~max_sum[i]~~ = ~~current_sum~~
	~~if i >~~= w:
	~~current_sum -~~= ~~v[i - w]~~
	~~if current_sum + max_sum[i - w] > max_sum[i]:~~
	~~max_sum[i] = current_sum + max_sum[i - w]~~

	~~with open~~(~~"ksum2.out", "w"~~) ~~as fout~~:		# Parcurgem vectorul și calculăm suma maximă
	~~fout.write(str(max_sum~~[~~n - 1~~]~~) + "\n")~~		for i in range(len(arr)):
			# Adăugăm elementul curent la suma curentă
			cur_sum += arr[i]

	~~print("Datele sunt introduse corect.")~~		# Dacă secvența devine prea lungă, scădem primul element din ea
			if i >= K:
			cur_sum -= arr[i-K]

			# Dacă secvența este suficient de lungă, verificăm dacă suma ei este maximă
			if i >= W-1:
			if cur_sum > max_sum:
			max_sum = cur_sum
			start = i-W+1
			end = i

			# Dacă suma curentă devine negativă, o resetăm la 0 și mutăm începutul secvenței
			if cur_sum < 0:
			cur_sum = 0

			return max_sum

	if __name__ == "__main__":
	n, k, w, v = ~~read_input~~()		if __name__ == '__main__':
	~~solve~~(n, k, w, v)		# Citim datele de intrare
			N, K, W = map(int, input().split())
			arr = list(map(int, input().split()))

			# Verificăm dacă datele de intrare sunt corecte
			if not validate_input(N, K, W, arr):
			print('Datele nu corespund restricțiilor impuse.')
			else:
			# Calculăm suma maximă și o afișăm
			max_sum = max_sequence_sum(arr, K, W)
			print(max_sum)


Line 81:		Line 104:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Acest cod începe prin citirea datelor~~ de intrare ~~din fișierul "ksum2~~.~~in". Acestea constau în trei numere întregi~~, n, k și w, ~~reprezentând numărul de elemente~~ din vectorul de ~~intrare, lungimea subsecvenței și lungimea maximă a subsecvenței care poate fi adunată pentru a obține~~ cel ~~mai mare sumă, respectiv un vector de n elemente reprezentând valorile vectorului~~.		Funcția validate_input primește patru argumente: N, K, W și arr. Această funcție validează datele de intrare pentru a se asigura că ele respectă restricțiile impuse în enunțul problemei. Mai exact, verifică dacă N, K și W se încadrează în intervalul specificat, iar elementele din vectorul arr sunt numere întregi de cel mult patru cifre. Funcția returnează True dacă datele de intrare sunt corecte și False în caz contrar.

	Funcția ~~"solve" primește aceste date~~ de intrare și ~~returnează suma maximă a unei subsecvențe de lungime k~~ în ~~care se poate aduna orice subsecvență de lungime w~~.

	Funcția ~~"validate_output" este folosită pentru~~ a ~~valida rezultatul obținut~~. ~~Aceasta citește valoarea așteptată din fișierul "ksum2~~.~~out"~~ și ~~compară cu valoarea obținută~~, ~~returnând True~~ dacă ~~sunt egale~~ și ~~False în caz contrar~~.		Funcția max_sequence_sum primește trei argumente: arr, K și W. Această funcție calculează suma maximă a unei secvențe (elemente adiacente) din vectorul dat, de lungime cel puțin K și cel mult W. Pentru a realiza aceasta, parcurge vectorul dat și calculează suma tuturor secvențelor de lungime între K și W. În timpul parcurgerii, menține suma curentă și, dacă aceasta devine negativă, o resetează la 0 și mută începutul secvenței. Dacă suma curentă depășește maximul anterior, aceasta devine noua sumă maximă. Funcția returnează suma maximă calculată.

	În ~~final~~, se apelează ~~funcțiile~~ pentru a ~~citi~~ datele ~~de intrare~~, ~~a calcula rezultatul~~ și ~~a valida~~ rezultatul ~~obținut~~. Se afișează ~~rezultatul obținut și o valoare booleană care indică dacă rezultatul este valid sau nu~~.		În blocul de cod if __name__ == '__main__', se citesc datele de intrare și se apelează funcția validate_input pentru a verifica dacă datele sunt introduse corect. Dacă datele sunt introduse corect, se calculează suma maximă folosind funcția max_sequence_sum și se afișează rezultatul. În caz contrar, se afișează un mesaj de eroare.

Flaviu at 08:13, 3 May 2023

2023-05-03T08:13:45Z

← Older revision		Revision as of 08:13, 3 May 2023
Line 12:		Line 12:
	Fișierul de ieșire ksum2.out va conține:		Fișierul de ieșire ksum2.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 '''rima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W''', 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 18:		Line 18:
	* elementele şirului vor avea cel mult 4 cifre		* elementele şirului vor avea cel mult 4 cifre
	* o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător		* o secvență 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
	: 8:		: ksum2.in
			: 8
	: 12 10 15 17 17		: 12 10 15 17 17
	: 10 12 14		: 10 12 14
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: ksum2.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 3		: 3

			== Exemplu 1 ==
			; Intrare
			: ksum2.in
			: 8
			: 1 2 3 4 5 6
			: -0,12 123 0 1 -2 -3 1,23
			; Ieșire
			: ksum2.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 15:00, 28 April 2023

2023-04-28T15:00:39Z

← Older revision		Revision as of 15:00, 28 April 2023
Line 10:		Line 10:

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ksum2.out va conține pe ~~prima linie~~ numărul S, reprezentând ~~suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W~~.		Fișierul de ieșire ksum2.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:
	: 10 12 14		: 10 12 14
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 3		: 3

Line 50:		Line 54:
	if current_sum + max_sum[i - w] > max_sum[i]:		if current_sum + max_sum[i - w] > max_sum[i]:
	max_sum[i] = current_sum + max_sum[i - w]		max_sum[i] = current_sum + max_sum[i - w]
	~~return max_sum[n - 1]~~
			with open("ksum2.out", "w") as fout:
	~~def validate_output(output_file, result):~~		fout.write(str(max_sum[n - 1]) + "\n")
	with open(~~output_file~~, "r") as ~~fin~~:
	~~expected_result = int(fin~~.~~readline~~(~~).strip~~())		print("Datele sunt introduse corect.")
	~~return result == expected_result~~

	if __name__ == "__main__":		if __name__ == "__main__":
	n, k, w, v = read_input()		n, k, w, v = read_input()
	~~result =~~ solve(n, k, w, v)		solve(n, k, w, v)
	~~is_valid = validate_output("ksum2.out", result)~~
	~~print(result)~~
	~~print("Result is valid:", is_valid)~~


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru rezolvarea acestei probleme putem adapta algoritmul lui Kadane pentru a căuta suma maximă a unei secvențe de lungime cel puțin K și cel mult W.~~

	~~Putem folosi o listă auxiliară max_sum~~ în care ~~vom memora suma maximă până la fiecare element din~~ vector. ~~În mod similar cu algoritmul lui Kadane, dacă~~ suma ~~până la un anumit element este negativă, o vom ignora și vom începe o nouă secvență~~ de ~~la acel element~~.		Acest cod începe prin citirea datelor de intrare din fișierul "ksum2.in". Acestea constau în trei numere întregi, n, k și w, reprezentând numărul de elemente din vectorul de intrare, lungimea subsecvenței și lungimea maximă a subsecvenței care poate fi adunată pentru a obține cel mai mare sumă, respectiv un vector de n elemente reprezentând valorile vectorului.

			Funcția "solve" primește aceste date de intrare și returnează suma maximă a unei subsecvențe de lungime k în care se poate aduna orice subsecvență de lungime w.

	~~Diferența constă în faptul că trebuie să verificăm la fiecare pas dacă am ajuns la un element~~ din ~~intervalul [K~~, ~~W], iar~~ în ~~acest~~ caz~~, dacă suma maximă până la acel element este mai mare decât suma maximă găsită anterior, vom actualiza această valoare~~.		Funcția "validate_output" este folosită pentru a valida rezultatul obținut. Aceasta citește valoarea așteptată din fișierul "ksum2.out" și compară cu valoarea obținută, returnând True dacă sunt egale și False în caz contrar.

	În final, ~~vom returna suma maximă găsită~~ pentru ~~o secvență~~ de ~~lungime cel puțin K~~ și ~~cel mult W~~.		În final, se apelează funcțiile pentru a citi datele de intrare, a calcula rezultatul și a valida rezultatul obținut. Se afișează rezultatul obținut și o valoare booleană care indică dacă rezultatul este valid sau nu.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3846/ksum2 3846 - KSum2] ---- == Cerinţa == După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K și cel mult W. A zis să vă întrebe pe voi cum se face. == Date de intrare == Fișierul de intrare ksum2.in conține pe prima linie numerele N, K ș...

2023-04-18T07:26:37Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3846/ksum2 3846 - KSum2] ---- == Cerinţa == După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K și cel mult W. A zis să vă întrebe pe voi cum se face. == Date de intrare == Fișierul de intrare ksum2.in conține pe prima linie numerele N, K ș...

New page

Sursa: [https://www.pbinfo.ro/probleme/3846/ksum2 3846 - KSum2]
----
== Cerinţa ==
După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K și cel mult W. A zis să vă întrebe pe voi cum se face.

== Date de intrare ==
Fișierul de intrare ksum2.in conține pe prima linie numerele N, K și W, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

== Date de ieșire ==
Fișierul de ieșire ksum2.out va conține pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000
* elementele şirului vor avea cel mult 4 cifre
* o secvență 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
: 8:
: 12 10 15 17 17
: 10 12 14
; Ieșire
: 3

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3846 - KSum2

def read_input():
with open("ksum2.in", "r") as fin:
n, k, w = map(int, fin.readline().split())
v = list(map(int, fin.readline().split()))
return n, k, w, v

def solve(n, k, w, v):
max_sum = [0] * n
current_sum = 0
for i in range(n):
current_sum += v[i]
if i >= k:
current_sum -= v[i - k]
if i >= k - 1:
max_sum[i] = max(max_sum[i - 1], current_sum)
else:
max_sum[i] = current_sum
if i >= w:
current_sum -= v[i - w]
if current_sum + max_sum[i - w] > max_sum[i]:
max_sum[i] = current_sum + max_sum[i - w]
return max_sum[n - 1]

def validate_output(output_file, result):
with open(output_file, "r") as fin:
expected_result = int(fin.readline().strip())
return result == expected_result

if __name__ == "__main__":
n, k, w, v = read_input()
result = solve(n, k, w, v)
is_valid = validate_output("ksum2.out", result)
print(result)
print("Result is valid:", is_valid)

</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru rezolvarea acestei probleme putem adapta algoritmul lui Kadane pentru a căuta suma maximă a unei secvențe de lungime cel puțin K și cel mult W.

Putem folosi o listă auxiliară max_sum în care vom memora suma maximă până la fiecare element din vector. În mod similar cu algoritmul lui Kadane, dacă suma până la un anumit element este negativă, o vom ignora și vom începe o nouă secvență de la acel element.

Diferența constă în faptul că trebuie să verificăm la fiecare pas dacă am ajuns la un element din intervalul [K, W], iar în acest caz, dacă suma maximă până la acel element este mai mare decât suma maximă găsită anterior, vom actualiza această valoare.

În final, vom returna suma maximă găsită pentru o secvență de lungime cel puțin K și cel mult W.