0854 - Secvente1 - Revision history

Flaviu at 20:15, 14 May 2023

2023-05-14T20:15:38Z

← Older revision		Revision as of 20:15, 14 May 2023
Line 26:		Line 26:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: 4~~

	== Rezolvare ==		== Rezolvare ==
Line 33:		Line 33:
	# 0854 - Secvente1		# 0854 - Secvente1

	def ~~minim_secvente_disjuncte~~(n, k, arr):		def validare_date_intrare(n, k, arr):
			if not (1 <= k < n <= 100000):
			return False
			if any(num >= 1000000000 for num in arr):
			return False
			return True


			def rezolvare_problema(n, k, arr):
	count = 0		count = 0
	odd_count = 0		odd_count = 0

	for num in arr:		for num in arr:
	if num % 2 != 0:		if num % 2 != 0:
	odd_count += 1		odd_count += 1

	if odd_count > k:		if odd_count > k:
	count += 1		count += 1
	odd_count = 1		odd_count = 1

	return count + 1		return count + 1


	if __name__ == "__main__":		if __name__ == "__main__":
	~~n, k~~ = ~~map(~~int~~, input().split())~~		t = int(input())
	~~arr = list(map~~(~~int,~~ input(~~).split()~~))

	~~if not (1 <= k < n <= 100000) or any(num >= 1000000000~~ for ~~num~~ in ~~arr~~):		for i in range(t):
	~~print~~(~~"Datele nu corespund restricțiilor impuse~~.")		n, k = map(int, input().split())
	~~else:~~		arr = list(map(int, input().split()))
	~~print("Datele sunt introduse corect."~~)
	~~print~~(~~minim_secvente_disjuncte~~(n, ~~k, arr~~))

			if not validare_date_intrare(n, k, arr):
			print("Datele nu corespund restricțiilor impuse.")
			else:
			print("Datele sunt introduse corect.")
			print(rezolvare_problema(n, k, arr))

	</syntaxhighlight>		</syntaxhighlight>
	== Expliacatie Rezolvare ==		== Expliacatie Rezolvare ==

	Funcția ~~minim_secvente_disjuncte primește argumentele n, k, și arr.~~		Funcția validare_date_intrare verifică dacă datele de intrare respectă restricțiile problemei și returnează True dacă acestea sunt corecte, False altfel.
	~~Inițializăm două variabile: count (pentru a contoriza numărul~~ de ~~secvențe)~~ și ~~odd_count (pentru a număra câte elemente impare~~ sunt ~~într-o secvență).~~
	~~Parcurgem lista arr și pentru fiecare element:~~		Funcția rezolvare_problema primește cele 3 argumente și aplică algoritmul descris în cerință pentru a determina numărul minim de secvențe disjuncte care conțin cel puțin k numere impare.
	~~Dacă elementul este impar~~, ~~creștem odd_count cu 1~~.
	~~Dacă odd_count devine mai mare decât k, înseamnă că trebuie să începem o nouă secvență, deci creștem count cu 1 și resetăm odd_count la 1.~~		În funcția if __name__ == "__main__", se citește numărul de seturi de date, apoi pentru fiecare set de date citesc datele de intrare. Se validează datele de intrare folosind funcția validare_date_intrare și se afișează rezultatul folosind funcția rezolvare_problema.
	Funcția ~~returnează count + 1, deoarece ultima secvență nu va fi inclusă~~ în numărul de secvențe ~~contorizate~~.
	În funcția if __name__ == "__main__"~~: citim~~ datele de intrare~~, validăm~~ datele~~, apoi apelăm~~ funcția ~~minim_secvente_disjuncte~~ și ~~afișăm~~ rezultatul.

Flaviu at 21:32, 13 May 2023

2023-05-13T21:32:13Z

← Older revision		Revision as of 21:32, 13 May 2023
Line 33:		Line 33:
	# 0854 - Secvente1		# 0854 - Secvente1

	def ~~citire():~~		def minim_secvente_disjuncte(n, k, arr):
	~~n, k = map(int, input().split())~~		count = 0
	~~sir = list(map(int, input().split()))~~		odd_count = 0
	~~return n, k, sir~~

	~~def rezolvare~~(n, k, ~~sir~~):
	~~secventa~~ = []
	~~secvente~~ = 0

	for i in ~~range(n)~~:		for num in arr:
	if ~~sir[i]~~ % 2 == 0:		if num % 2 != 0:
	~~continue # Ignoram elementele pare~~		odd_count += 1
	~~if len(secventa) == 0 or len(secventa[-1]) == k:~~
	~~secventa.append([sir[i]]) # Cream o secventa noua~~
	~~secvente~~ += 1
	~~else:~~
	~~secventa[-1].append(sir[i]) # Adaugam elementul la ultima secventa~~

	return ~~secvente~~		if odd_count > k:
			count += 1
			odd_count = 1

			return count + 1

	~~def validare~~(~~secvente~~, ~~rezultat~~):		if __name__ == "__main__":
	~~assert secvente~~ =~~= rezultat~~, ~~f"Secvente: {secvente}, Rezultat asteptat: {rezultat}"~~		n, k = map(int, input().split())
			arr = list(map(int, input().split()))

	if ~~__name__~~ =~~= '__main__':~~		if not (1 <= k < n <= 100000) or any(num >= 1000000000 for num in arr):
	n~~, k, sir~~ = ~~citire~~()		print("Datele nu corespund restricțiilor impuse.")
	~~rez = rezolvare~~(~~n, k, sir~~)		else:
	~~if rez != -1~~:
	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	print(~~rez~~)		print(minim_secvente_disjuncte(n, k, arr))
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse."~~)


Line 69:		Line 61:
	== Expliacatie Rezolvare ==		== Expliacatie Rezolvare ==

	~~Am definit mai întâi funcția citire() care citește numerele de la tastatură~~ și ~~returnează cele trei valori sub forma unei tuple~~.		Funcția minim_secvente_disjuncte primește argumentele n, k, și arr.
	~~Funcția rezolvare~~(~~) primește cele trei valori citite și calculează~~ numărul ~~minim~~ de secvențe ~~necesare.~~		Inițializăm două variabile: count (pentru a contoriza numărul de secvențe) și odd_count (pentru a număra câte elemente impare sunt într-o secvență).
	~~Iterăm prin șir~~ și ~~construim secvențe de~~ elemente impare ~~care au cel mult k elemente~~. ~~Pentru~~ fiecare ~~secvență~~, ~~verificăm dacă~~ mai ~~putem adăuga elemente impare la ea sau~~ trebuie să începem o secvență ~~nouă.~~		Parcurgem lista arr și pentru fiecare element:
	~~Incrementăm un contor de secvențe~~ la ~~fiecare început de secvență~~.		Dacă elementul este impar, creștem odd_count cu 1.
	Funcția ~~validare() compară rezultatul obținut cu cel așteptat și aruncă o excepție~~ în ~~cazul în care nu se potrivește~~.		Dacă odd_count devine mai mare decât k, înseamnă că trebuie să începem o nouă secvență, deci creștem count cu 1 și resetăm odd_count la 1.
	În ~~final~~, ~~am adăugat un test pentru a verifica~~ funcția ~~rezolvare()~~ și ~~am afișat~~ rezultatul.		Funcția returnează count + 1, deoarece ultima secvență nu va fi inclusă în numărul de secvențe contorizate.
			În funcția if __name__ == "__main__": citim datele de intrare, validăm datele, apoi apelăm funcția minim_secvente_disjuncte și afișăm rezultatul.

Flaviu at 07:26, 3 May 2023

2023-05-03T07:26:33Z

← Older revision		Revision as of 07:26, 3 May 2023
Line 8:		Line 8:
	== 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 '''va afișa pe ecran numărul minim de secvențe 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 ==
	* 1 ≤ k < n ≤ 100.000		* 1 ≤ k < n ≤ 100.000
	* cele n numere citite vor fi mai mici decât 1.000.000.000		* cele n numere citite vor fi mai mici decât 1.000.000.000
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 7 2		: 7 2
	: 4 3 4 9 9 1 8		: 4 3 4 9 9 1 8
			; Ieșire
			: Datele sunt introduse corect.
			: 2
			== Exemplu 2 ==
			; Intrare
			: 7 2
			: 2 3 4 9 1 1 8
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: 2		: 4


	== Rezolvare ==		== Rezolvare ==

Flaviu at 18:21, 27 April 2023

2023-04-27T18:21:04Z

← Older revision		Revision as of 18:21, 27 April 2023
Line 7:		Line 7:

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul~~ va afișa pe ecran ~~numărul minim de secvențe C~~.		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 17:		Line 18:
	: 4 3 4 9 9 1 8		: 4 3 4 9 9 1 8
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: 2		: 2

Line 24:		Line 26:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 0854 - Secvente1		# 0854 - Secvente1

	def citire():		def citire():
	n, k = map(int, input().split())		n, k = map(int, input().split())
Line 48:		Line 51:

	if __name__ == '__main__':		if __name__ == '__main__':
	~~# Teste~~
	n, k, sir = citire()		n, k, sir = citire()
	rez = rezolvare(n, k, sir)		rez = rezolvare(n, k, sir)
	~~validare~~(rez~~, 2~~) ~~# Pentru sirul [3, 9, 9, 1] avem 2 secvente de lungime maxima k=2~~		if rez != -1:
	print(~~rez~~)		print("Datele sunt introduse corect.")
			print(rez)
			else:
			print("Datele nu corespund restricțiilor impuse.")


	</syntaxhighlight>		</syntaxhighlight>

Flaviu at 19:58, 17 April 2023

2023-04-17T19:58:05Z

@@ Line 24: / Line 24: @@
 <syntaxhighlight lang="python" line>
 # 0854 - Secvente1
-n, k = map(int, input().split())
+def rezolvare(n, k, sir):
-a = list(map(int, input().split()))
+    secventa = []
-num_secvente = 0
+def validare(secvente, rezultat):
-num_impares_curent = 0
+     assert secvente == rezultat, f"Secvente: {secvente}, Rezultat asteptat: {rezultat}"
-</syntaxhighlight>
+Am definit mai întâi funcția citire() care citește numerele de la tastatură și returnează cele trei valori sub forma unei tuple.

Flaviu at 21:35, 21 March 2023

2023-03-21T21:35:42Z

← Older revision		Revision as of 21:35, 21 March 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/71/~~reducere~~ 0854 - Secvente1]		Sursa: [https://www.pbinfo.ro/probleme/854/secvente1 0854 - Secvente1]
	----		----
	== Cerinţa ==		== Cerinţa ==

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0854 - Secvente1] ---- == Cerinţa == Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare. == Date de intrare == Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale ș...

2023-03-21T21:35:08Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0854 - Secvente1] ---- == Cerinţa == Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare. == Date de intrare == Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale ș...

New page

Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0854 - Secvente1]
----
== Cerinţa ==
Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare.
== Date de intrare ==
Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale șirului

== Date de ieșire ==
Programul va afișa pe ecran numărul minim de secvențe C.

== Restricţii şi precizări ==
* 1 ≤ k < n ≤ 100.000
* cele n numere citite vor fi mai mici decât 1.000.000.000
== Exemplu ==
; Intrare
: 7 2
: 4 3 4 9 9 1 8
; Ieșire
: 2

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0854 - Secvente1

n, k = map(int, input().split())
a = list(map(int, input().split()))

num_secvente = 0
num_impares_curent = 0

for i in range(n):
if a[i] % 2 == 1 and num_impares_curent < k:
num_impares_curent += 1
else:
num_secvente += 1
num_impares_curent = 1 if a[i] % 2 == 1 else 0

print(num_secvente + (num_impares_curent > 0))

</syntaxhighlight>