3844 - KSum - Revision history

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

2023-05-14T22:40:16Z

Date de ieșire

← Older revision		Revision as of 22:40, 14 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."''' ksum.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''', 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 ksum.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''', 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 ==

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

2023-05-14T22:38:37Z

Date de ieșire

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

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire ksum.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 numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''' ksum.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''', 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:58, 14 May 2023

2023-05-14T21:58:47Z

← Older revision		Revision as of 21:58, 14 May 2023
Line 22:		Line 22:
	: 5 4 -10 1 2 3		: 5 4 -10 1 2 3
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: ksum.out		: ksum.out
	~~: Datele sunt introduse correct.~~
	: 6		: 6

Line 32:		Line 32:
	: 2,34 -2 -3 -1 0 99 100		: 2,34 -2 -3 -1 0 99 100
	; Ieșire		; Ieșire
	~~: ksum.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 42:		Line 41:
	# 3844 - KSum		# 3844 - KSum

	def ~~read_input_file~~():		def validare_date(n, k, w):
	~~with open("ksum.in", "r") as input_file:~~		return 1 <= k <= w <= n <= 100000
	n, k = ~~map(int, input_file.readline().split())~~
	v = ~~list(map(int, input_file.readline().split()))~~
	~~return n, k, v~~

	def ~~ksum~~(n, k, v):		def k_sum(n, k, w, numere):
	s = [0] * (n ~~+ 1)~~		if not validare_date(n, k, w):
	~~for i in range(1~~, ~~n + 1):~~		print("Datele nu corespund restricțiilor impuse.")
	~~s[i] = s[i-1] + v[i-1]~~		return
	~~m = [0] * (n + 1)~~
	~~for i in range(~~k, ~~n + 1~~):
	~~m[i] = max~~(~~m[i-1], s[i] - s[i-k]~~)
	return ~~max(m)~~

	~~def write_output_file(result):~~		print("Datele sunt introduse corect.")
	~~with open~~("~~ksum~~.~~out", "w~~"~~) as output_file:~~
	~~output_file.write(str(result)~~)

	~~if __name__ == '__main__':~~		# caz particular - vectorul este deja de lungime cel putin k
	n, k~~, v = read_input_file()~~		if n >= k:
	~~result~~ = ~~ksum(n,~~ k~~, v)~~		max_sum = sum(numere[:k])
	~~if result > 0~~:
	~~print~~(~~"Datele sunt introduse corect."~~)
	else:		else:
	~~print~~("~~Datele nu corespund restricțiilor impuse~~.")		max_sum = sum(numere)
	~~write_output_file~~(~~result~~)
			current_sum = max_sum

			# parcurgem vectorul si actualizam suma maxima intalnita pana acum
			for i in range(k, n):
			current_sum += numere[i] - numere[i-k]
			max_sum = max(max_sum, current_sum)

			with open('ksum.out', 'w') as f:
			f.write(str(max_sum))


			if __name__ == "__main__":
			with open('ksum.in', 'r') as f:
			n, k, w = map(int, f.readline().split())
			numere = list(map(int, f.readline().split()))

			k_sum(n, k, w, numere)


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~functia read_input_file citeste datele de intrare din fisier si le returneaza sub forma de tuplu~~ (n, k, v), ~~unde n este numarul~~ de elemente din vector, k este ~~numarul minim~~ de elemente ~~consecutive care trebuie sa fie considerate in calculul sumei~~, ~~iar v este lista~~ cu ~~elementele vectorului~~.		Funcția validare_date(n, k, v), care primește ca argumente numărul de elemente din vector n, lungimea minimă a secvenței cerute k, și vectorul v de n elemente. Aceasta verifică dacă datele de intrare respectă restricțiile impuse de problema și returnează True dacă datele sunt valide și False altfel. Verificarea se face astfel:
	~~functia ksum primeste~~ ca ~~parametri~~ n, k si v~~, si calculeaza suma maxima~~ a unei ~~secvente~~ de lungime cel ~~putin~~ k. ~~Pentru~~ a ~~gasi~~ suma ~~maxima se calculeaza~~ suma ~~elementelor de~~ la 1 la i, ~~pentru fiecare i din vectorul s~~. ~~De asemenea~~, ~~se construieste un alt vector~~, ~~m, care contine pentru fiecare pozitie i~~ din ~~vectorul s~~, ~~suma maxima a unei secvente~~ de ~~lungime cel putin k care se termina in pozitia i. Suma maxima se va gasi in ultimul element al vectorului m~~.
	~~functia write_output_file scrie rezultatul obtinut in fisierul de iesire.~~		Verifică dacă lungimea minimă a secvenței cerute este mai mică sau egală cu numărul total de elemente din vector, k <= n.
	~~in cadrul~~ if __name__ == '__main__': se ~~apeleaza cele trei functii in ordinea: citirea datelor~~ de intrare~~, calculul solutiei si scrierea rezultatului~~ in ~~fisierul de iesire~~.		Verifică dacă numerele din vector au o valoare absolută mai mică sau egală cu 1000, utilizând funcția abs().
			Returnează True dacă toate aceste condiții sunt satisfăcute, altfel returnează False.
			Funcția rezolva(n, k, v), care primește aceleași argumente ca și funcția validare_date, adică numărul de elemente din vector n, lungimea minimă a secvenței cerute k, și vectorul v de n elemente. Aceasta returnează valoarea maximă a unei secvențe de lungime cel puțin k din vectorul dat.

			Algoritmul utilizat pentru a găsi această valoare este următorul:

			Inițializăm o variabilă suma_max cu valoarea 0, o variabilă suma_curenta cu valoarea 0, și o variabilă inceput_secventa cu valoarea 0.
			Parcurgem elementele vectorului v folosind un iterator i.
			Adunăm elementul v[i] la suma curentă a secvenței, suma_curenta.
			Dacă suma curentă este mai mică decât 0, resetăm suma curentă și inceputul secvenței curente la i+1.
			Dacă suma curentă este mai mare decât suma_max, actualizăm suma_max și inceput_secventa la inceput_secventa_curenta.
			La final, returnăm suma_max.
			Funcția citeste_date_intrare(nume_fisier), care primește numele unui fișier de intrare și returnează valorile n, k și vectorul v de n elemente citite din fișierul respectiv. Această funcție citește datele din fișierul de intrare folosind funcția with open() as f, apoi separă numerele citite dintr-un șir de caractere într-o listă de numere întregi folosind funcția map().

			În funcția principală if __name__ == '__main__', mai întâi se apelează funcția citeste_date_intrare() pentru a citi datele de intrare din fișierul ksum.in.

Flaviu at 08:12, 3 May 2023

2023-05-03T08:12:32Z

← Older revision		Revision as of 08:12, 3 May 2023
Line 11:		Line 11:
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ksum.out va conține Dacă datele sunt introduse corect, pe ecran se va afișa:		Fișierul de ieșire ksum.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."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K''', 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 ≤ 100.000		* 1 ≤ K <= W <= n ≤ 100.000
	* numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].		* numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: ksum.in
	: 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~~.		: ksum.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 6		: 6

			== Exemplu 2 ==
			; Intrare
			: ksum.in
			: 6 3 4
			: 2,34 -2 -3 -1 0 99 100
			; Ieșire
			: ksum.out
			: Datele nu corespund restricțiilor impuse.



	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:58, 28 April 2023

2023-04-28T14:58:52Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ksum.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~~.		Fișierul de ieșire ksum.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 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 49:		Line 52:
	n, k, v = read_input_file()		n, k, v = read_input_file()
	result = ksum(n, k, v)		result = ksum(n, k, v)
			if result > 0:
			print("Datele sunt introduse corect.")
			else:
			print("Datele nu corespund restricțiilor impuse.")
	write_output_file(result)		write_output_file(result)

Flaviu at 07:23, 18 April 2023

2023-04-18T07:23:34Z

← Older revision		Revision as of 07:23, 18 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/~~304~~/~~secvente~~ 3844 - KSum]		Sursa: [https://www.pbinfo.ro/probleme/3844/ksum 3844 - KSum]
	----		----
	== Cerinţa ==		== Cerinţa ==
Line 13:		Line 13:

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 ≤ K <= n ≤ 100.000		* 1 ≤ K <= W <= n ≤ 100.000
	* numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].		* numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].
	== Exemplu ==		== Exemplu ==
	; Intrare		; Intrare
	: 6 3		: 6 3 4
	: 5 4 -10 1 2 3		: 5 4 -10 1 2 3
	; Ieșire		; Ieșire
Line 27:		Line 27:
	# 3844 - KSum		# 3844 - KSum

	def ~~citeste_date_intrare~~():		def read_input_file():
	n = int(~~input~~())		with open("ksum.in", "r") as input_file:
	~~sir~~ = []		n, k = map(int, input_file.readline().split())
	~~for i in range~~(~~n):~~		v = list(map(int, input_file.readline().split()))
	~~sir.append~~(int(~~input~~()))		return n, k, v
	return ~~sir~~

	def ~~numara_secvente_crescatoare~~(~~sir~~):		def ksum(n, k, v):
	~~numar_secvente~~ = 0		s = [0] * (n + 1)
	~~lungime_maxima = 1~~		for i in range(1, n + 1):
	~~lungime_curenta =~~ 1		s[i] = s[i-1] + v[i-1]
	for i in range(1, ~~len(sir)~~):		m = [0] * (n + 1)
	~~if sir~~[i] >= ~~sir~~[i-1]:		for i in range(k, n + 1):
	~~lungime_curenta~~ += 1		m[i] = max(m[i-1], s[i] - s[i-k])
	~~else:~~		return max(m)
	~~if lungime_curenta > lungime_maxima:~~
	~~lungime_maxima~~ = ~~lungime_curenta~~
	~~numar_secvente = 1~~
	~~elif lungime_curenta == lungime_maxima:~~
	~~numar_secvente~~ +~~= 1~~
	~~lungime_curenta =~~ 1
	~~if lungime_curenta > lungime_maxima:~~
	~~lungime_maxima = lungime_curenta~~
	~~numar_secvente =~~ 1
	~~elif lungime_curenta == lungime_maxima~~:
	~~numar_secvente +~~= 1
	return ~~numar_secvente~~

	def ~~valideaza~~(~~sir~~, ~~numar_secvente~~):		def write_output_file(result):
	~~assert len~~(~~sir~~) ~~> 0~~		with open("ksum.out", "w") as output_file:
	~~assert numar_secvente >~~= 0		output_file.write(str(result))

			if __name__ == '__main__':
			n, k, v = read_input_file()
			result = ksum(n, k, v)
			write_output_file(result)

	~~if __name__ == "__main__":~~
	~~sir = citeste_date_intrare()~~
	~~numar_secvente = numara_secvente_crescatoare(sir)~~
	~~valideaza(sir, numar_secvente)~~
	~~print(numar_secvente)~~

	</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~~.		functia read_input_file citeste datele de intrare din fisier si le returneaza sub forma de tuplu (n, k, v), unde n este numarul de elemente din vector, k este numarul minim de elemente consecutive care trebuie sa fie considerate in calculul sumei, iar v este lista cu elementele vectorului.
			functia ksum primeste ca parametri n, k si v, si calculeaza suma maxima a unei secvente de lungime cel putin k. Pentru a gasi suma maxima se calculeaza suma elementelor de la 1 la i, pentru fiecare i din vectorul s. De asemenea, se construieste un alt vector, m, care contine pentru fiecare pozitie i din vectorul s, suma maxima a unei secvente de lungime cel putin k care se termina in pozitia i. Suma maxima se va gasi in ultimul element al vectorului m.
			functia write_output_file scrie rezultatul obtinut in fisierul de iesire.
			in cadrul if __name__ == '__main__': se apeleaza cele trei functii in ordinea: citirea datelor de intrare, calculul solutiei si scrierea rezultatului in fisierul de iesire.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3844 - KSum] ---- == Cerinţa == După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K 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. A zis să vă întrebe pe voi cum se face. == Date de intrare == Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea l...

2023-04-18T07:21:11Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3844 - KSum] ---- == Cerinţa == După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K 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. A zis să vă întrebe pe voi cum se face. == Date de intrare == Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea l...

New page

Sursa: [https://www.pbinfo.ro/probleme/304/secvente 3844 - KSum]
----
== Cerinţa ==
După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K 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. A zis să vă întrebe pe voi cum se face.

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

== Date de ieșire ==
Fișierul de ieșire ksum.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.

== Restricţii şi precizări ==
* 1 ≤ K <= n ≤ 100.000
* numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].
== Exemplu ==
; Intrare
: 6 3
: 5 4 -10 1 2 3
; Ieșire
: 6

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3844 - KSum

def citeste_date_intrare():
n = int(input())
sir = []
for i in range(n):
sir.append(int(input()))
return sir

def numara_secvente_crescatoare(sir):
numar_secvente = 0
lungime_maxima = 1
lungime_curenta = 1
for i in range(1, len(sir)):
if sir[i] >= sir[i-1]:
lungime_curenta += 1
else:
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
numar_secvente = 1
elif lungime_curenta == lungime_maxima:
numar_secvente += 1
lungime_curenta = 1
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
numar_secvente = 1
elif lungime_curenta == lungime_maxima:
numar_secvente += 1
return numar_secvente

def valideaza(sir, numar_secvente):
assert len(sir) > 0
assert numar_secvente >= 0

if __name__ == "__main__":
sir = citeste_date_intrare()
numar_secvente = numara_secvente_crescatoare(sir)
valideaza(sir, numar_secvente)
print(numar_secvente)

</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.