3937 - KSum3 - Revision history

Flaviu at 21:31, 14 May 2023

2023-05-14T21:31:31Z

← Older revision		Revision as of 21:31, 14 May 2023
Line 76:		Line 76:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	validate_input(n, k, w, arr): Această funcție ~~validează datele~~ de ~~intrare. Verifică dacă valorile N~~, K și W ~~respectă restricțiile impuse~~ și ~~dacă dimensiunea vectorului~~ este ~~în concordanță cu N. Returnează True dacă~~ datele ~~sunt valide și False în caz contrar~~.		validate_input(N, K, W, arr): Această funcție primește patru parametri: N, K, W și arr, reprezentând numărul de elemente, limitele K și W, și lista de numere întregi arr. Scopul acestei funcții este să valideze datele de intrare conform restricțiilor impuse. Verificările includ:

	~~find_max_subsequence_sum(n~~, k, w, ~~arr): Această funcție calculează suma maximă a unei subsecvențe care respectă condițiile date. Verifică mai întâi validitatea datelor de intrare utilizând~~ funcția ~~validate_input()~~. ~~Apoi~~, ~~parcurge vectorul de la stânga la dreapta și, pentru fiecare poziție~~, ~~calculează suma maximă a unei subsecvențe de lungime cuprinsă între K și W. Returnează suma maximă calculată~~.		Dacă K și W sunt în intervalul permis, adică 1 <= K <= W <= N <= 1000000.
			Dacă lungimea listei arr este egală cu N.
			Dacă oricare dintre numerele din lista arr depășește limitele [-1000000000, 1000000000].
			Dacă oricare dintre aceste condiții nu este îndeplinită, funcția returnează False, indicând că datele nu corespund restricțiilor. În caz contrar, funcția returnează True, semnificând că datele sunt introduse corect.

	~~Blocul if __name__ == "__main__"~~: este ~~locul~~ în ~~care se face citirea datelor~~ de intrare ~~și apelarea funcțiilor pentru rezolvarea problemei~~.		find_max_subsequence_sum(N, K, W, arr): Această funcție primește aceiași parametri ca și validate_input: N, K, W și arr. Scopul acestei funcții este să găsească suma maximă a unei subsecvențe cu lungimi cuprinse între K și W în lista arr. Funcția verifică întâi datele de intrare utilizând funcția validate_input. Dacă datele nu sunt valide, funcția returnează mesajul "Datele nu corespund restricțiilor impuse."

	~~Se deschide fișierul "ksum3~~.~~in"~~ pentru ~~citire~~ și se ~~citesc valorile N~~, K, ~~W de pe prima linie și elementele vectorului de pe a doua linie~~.		Dacă datele sunt valide, funcția inițializează max_sum cu o valoare negativă foarte mică și current_sum cu 0. Apoi, utilizează o buclă for pentru a itera prin lista arr. La fiecare pas, adaugă elementul curent la suma curentă current_sum. Dacă indicele curent i este mai mare sau egal cu K - 1, înseamnă că lungimea subsecvenței este cel puțin K, așa că compară current_sum cu max_sum și actualizează max_sum dacă este necesar. În final, se scade elementul din subsecvență care nu mai face parte din fereastra curentă, adică arr[i - K + 1], din current_sum.
	~~Se apelează~~ funcția ~~find_max_subsequence_sum() cu datele citite~~.
	~~Dacă rezultatul returnat~~ este ~~o sumă validă~~, se ~~afișează "Datele sunt introduse corect."~~ și ~~suma calculată. Altfel~~, se ~~afișează mesajul "Datele nu corespund restricțiilor impuse."~~		La sfârșit, funcția returnează max_sum, care reprezintă suma maximă a subsecvenței.

			if __name__ == "__main__": : Acesta este blocul principal al programului care va fi executat doar atunci când scriptul este rulat direct și nu importat ca modul în altă parte a codului. În acest bloc, se face citirea datelor utilizând funcția input() și map(), apoi se apelează funcția find_max_subsequence_sum

Flaviu at 21:28, 14 May 2023

2023-05-14T21:28:01Z

← Older revision		Revision as of 21:28, 14 May 2023
Line 37:		Line 37:
	# 3937 - KSum3		# 3937 - KSum3

	def ~~read_input~~():		def validate_input(N, K, W, arr):
	~~n, k, w~~ = ~~map~~(~~int, input~~()~~.split~~())		if not (1 <= K <= W <= N <= 1000000):
	~~array = list~~(~~map(int~~, ~~input(~~).~~split~~()))		return False
	~~return n, k, w, array~~		if len(arr) != N:
			return False
			if any(num < -1000000000 or num > 1000000000 for num in arr):
			return False
			return True


			def find_max_subsequence_sum(N, K, W, arr):
			if not validate_input(N, K, W, arr):
			return "Datele nu corespund restricțiilor impuse."

			max_sum = float("-inf")
			current_sum = 0

			for i in range(N):
			current_sum += arr[i]
			if i >= K - 1:
			max_sum = max(max_sum, current_sum)
			current_sum -= arr[i - K + 1]

	~~def maximum_subarray_sum(n, k, w, array):~~		return max_sum
	~~dp = [0] * (n + 1)~~
	~~prefix_sum = [0] * (n + 1)~~
	~~prefix_sum[0] = array[0]~~
	~~for i in range(1, n):~~
	~~prefix_sum[i] = prefix_sum[i - 1] + array[i]~~
	~~for length in range(k, w + 1):~~
	~~for i in range(length - 1, n):~~
	~~if i == length - 1:~~
	~~dp[i] = prefix_sum[i]~~
	~~else:~~
	~~dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])~~
	return ~~max(dp[k - 1:n])~~


	~~def validate_input(n, k, w, array):~~		if __name__ == "__main__":
	if ~~not (1 <= k <= w <~~= ~~n <~~= ~~1000000)~~:		N = int(input("Introduceti N: "))
	~~return False~~		K = int(input("Introduceti K: "))
	~~for num in array~~:		W = int(input("Introduceti W: "))
	~~if not~~ (~~-1000000000 <= num <= 1000000000~~):
	~~return False~~
	~~return True~~

			arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))

	~~if __name__ == '__main__':~~		result = find_max_subsequence_sum(N, K, W, arr)
	~~n, k, w, array = read_input()~~		print(result)
	~~if validate_input(n, k, w, array):~~
	result = ~~maximum_subarray_sum~~(n, k, w, ~~array~~)
	~~print("Datele sunt introduse corect.")~~
	print(result)
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse."~~)


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Funcția read_input~~() ~~citește~~ de ~~la tastatură numerele~~ N, K, W și ~~un vector de~~ N ~~numere întregi~~ și ~~le returnează~~.		validate_input(n, k, w, arr): Această funcție validează datele de intrare. Verifică dacă valorile N, K și W respectă restricțiile impuse și dacă dimensiunea vectorului este în concordanță cu N. Returnează True dacă datele sunt valide și False în caz contrar.
	~~Funcția maximum_subarray_sum~~(~~) primește N~~, K, ~~W și vectorul citit de la tastatură și returnează~~ suma maximă a unei subsecvențe ~~cu lungimile cuprinse între K și W~~. ~~Algoritmul folosește programarea dinamică~~ și calculează suma maximă a unei subsecvențe ~~pentru fiecare~~ lungime între K și W. ~~Pe baza acestor calcule se determină~~ suma maximă ~~a întregului vector~~.
	~~Funcția validate_input() primește~~ N, K, W și ~~vectorul citit~~ de ~~la tastatură și verifică dacă acestea respectă condițiile problemei~~.		find_max_subsequence_sum(n, k, w, arr): Această funcție calculează suma maximă a unei subsecvențe care respectă condițiile date. Verifică mai întâi validitatea datelor de intrare utilizând funcția validate_input(). Apoi, parcurge vectorul de la stânga la dreapta și, pentru fiecare poziție, calculează suma maximă a unei subsecvențe de lungime cuprinsă între K și W. Returnează suma maximă calculată.
	În funcția ~~principală se citesc~~ datele ~~de intrare~~, se ~~validează~~ și se ~~apelează funcția de calcul a sumei maxime a unei subsecvențe~~.
			Blocul if __name__ == "__main__": este locul în care se face citirea datelor de intrare și apelarea funcțiilor pentru rezolvarea problemei.

			Se deschide fișierul "ksum3.in" pentru citire și se citesc valorile N, K, W de pe prima linie și elementele vectorului de pe a doua linie.
			Se apelează funcția find_max_subsequence_sum() cu datele citite.
			Dacă rezultatul returnat este o sumă validă, se afișează "Datele sunt introduse corect." și suma calculată. Altfel, se afișează mesajul "Datele nu corespund restricțiilor impuse."

Flaviu at 08:00, 3 May 2023

2023-05-03T08:00:04Z

← Older revision		Revision as of 08:00, 3 May 2023
Line 11:		Line 11:
	== 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 maxima a unei subsecvențe care respectă condițiile din enunț'', 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 ≤ K ≤ W ≤ N ≤ 1.000.000		* 1 ≤ K ≤ W ≤ N ≤ 1.000.000
	* cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător		* cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 6 3 4		: 6 3 4
	: 5 4 -10 1 2 3		: 5 4 -10 1 2 3
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 6		: 6

			== Exemplu 1 ==
			; Intrare
			: 256
			: 5 4 -10 -3 -3 0 0 0
			; Ieșire
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:44, 28 April 2023

2023-04-28T14:44:34Z

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

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ~~ecran~~ numărul S, reprezentând ~~suma maxima a unei subsecvențe care respectă condițiile din enunț~~.		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 20:		Line 21:
	: 5 4 -10 1 2 3		: 5 4 -10 1 2 3
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 6		: 6

Line 31:		Line 34:
	array = list(map(int, input().split()))		array = list(map(int, input().split()))
	return n, k, w, array		return n, k, w, array


	def maximum_subarray_sum(n, k, w, array):		def maximum_subarray_sum(n, k, w, array):
Line 45:		Line 49:
	dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])		dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
	return max(dp[k - 1:n])		return max(dp[k - 1:n])


	def validate_input(n, k, w, array):		def validate_input(n, k, w, array):
Line 53:		Line 58:
	return False		return False
	return True		return True


	if __name__ == '__main__':		if __name__ == '__main__':
	n, k, w, array = read_input()		n, k, w, array = read_input()
	if validate_input(n, k, w, array):		if validate_input(n, k, w, array):
	~~print(~~maximum_subarray_sum(n, k, w, array))		result = maximum_subarray_sum(n, k, w, array)
			print("Datele sunt introduse corect.")
			print(result)
	else:		else:
	print("~~Input is not valid!~~")		print("Datele nu corespund restricțiilor impuse.")

Flaviu at 06:49, 18 April 2023

2023-04-18T06:49:41Z

← Older revision		Revision as of 06:49, 18 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/~~304~~/~~secvente~~ 3937 - KSum3]		Sursa: [https://www.pbinfo.ro/probleme/3937/ksum3 3937 - KSum3]
	----		----
	== Cerinţa ==		== Cerinţa ==

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3937 - KSum3] ---- == Cerinţa == Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W). == Date de intrare == Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi. == Date de ieșire == Programul va afișa pe ecran numărul S, reprezentând suma maxima a unei su...

2023-04-18T06:48:17Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3937 - KSum3] ---- == Cerinţa == Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W). == Date de intrare == Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi. == Date de ieșire == Programul va afișa pe ecran numărul S, reprezentând suma maxima a unei su...

New page

Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3937 - KSum3]
----
== Cerinţa ==
Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W).

== Date de intrare ==
Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi.

== Date de ieșire ==
Programul va afișa pe ecran numărul S, reprezentând suma maxima a unei subsecvențe care respectă condițiile din enunț.

== Restricţii şi precizări ==
* 1 ≤ K ≤ W ≤ N ≤ 1.000.000
* cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător
== Exemplu ==
; Intrare
: 6 3 4
: 5 4 -10 1 2 3
; Ieșire
: 6

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3937 - KSum3

def read_input():
n, k, w = map(int, input().split())
array = list(map(int, input().split()))
return n, k, w, array

def maximum_subarray_sum(n, k, w, array):
dp = [0] * (n + 1)
prefix_sum = [0] * (n + 1)
prefix_sum[0] = array[0]
for i in range(1, n):
prefix_sum[i] = prefix_sum[i - 1] + array[i]
for length in range(k, w + 1):
for i in range(length - 1, n):
if i == length - 1:
dp[i] = prefix_sum[i]
else:
dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
return max(dp[k - 1:n])

def validate_input(n, k, w, array):
if not (1 <= k <= w <= n <= 1000000):
return False
for num in array:
if not (-1000000000 <= num <= 1000000000):
return False
return True

if __name__ == '__main__':
n, k, w, array = read_input()
if validate_input(n, k, w, array):
print(maximum_subarray_sum(n, k, w, array))
else:
print("Input is not valid!")

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input() citește de la tastatură numerele N, K, W și un vector de N numere întregi și le returnează.
Funcția maximum_subarray_sum() primește N, K, W și vectorul citit de la tastatură și returnează suma maximă a unei subsecvențe cu lungimile cuprinse între K și W. Algoritmul folosește programarea dinamică și calculează suma maximă a unei subsecvențe pentru fiecare lungime între K și W. Pe baza acestor calcule se determină suma maximă a întregului vector.
Funcția validate_input() primește N, K, W și vectorul citit de la tastatură și verifică dacă acestea respectă condițiile problemei.
În funcția principală se citesc datele de intrare, se validează și se apelează funcția de calcul a sumei maxime a unei subsecvențe.