0071 - Reducere - Revision history

Flaviu at 20:14, 14 May 2023

2023-05-14T20:14:18Z

← Older revision		Revision as of 20:14, 14 May 2023
Line 51:		Line 51:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: 2~~
	~~: 3~~
	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===
Line 58:		Line 57:
	# 0071 - Reducere		# 0071 - Reducere

	def ~~can_reduce~~(A, B):		def se_poate_reduca_la_B(A, B):
			i = j = 0
	n = len(A)		n = len(A)
	m = len(B)		m = len(B)

	~~i = j = 0~~
	while i < n and j < m:		while i < n and j < m:
	if A[i] == B[j]:		if A[i] == B[j]:
Line 68:		Line 66:
	j += 1		j += 1
	else:		else:
	~~sum_a~~ = A[i]		s = A[i]
	~~sum_b~~ = ~~B[j]~~		i += 1
	while i < n-1 and ~~sum_a !~~= ~~sum_b:~~		while i < n and s < B[j]:
			s += A[i]
	i += 1		i += 1
	~~sum_a += A[i]~~		if s != B[j]:
	~~while j < m-1 and sum_a~~ !~~= sum_b:~~		return 0
	~~j += 1~~		j += 1
	~~sum_b +~~= B[j]
	~~if sum_a != sum_b~~:
	return ~~False~~

	return j == m		return j == m

			def validare(n, A, m, B):
			if not(1 <= n <= 1000) or not(1 <= m <= 1000):
			return False
			if not all(1 <= a <= 10000 for a in A) or not all(1 <= b <= 10000 for b in B):
			return False
			return True

	if __name__ == "__main__":		if __name__ == "__main__":
	T = int(input())		T = int(input())
	for i in range(T):		if T <= 0 or T > 10:
	n = int(input())		print("Datele nu corespund restricțiilor impuse.")
	A = list(map(int, input().split()))		else:
	m = int(input())		print("Datele sunt introduse corect.")
	B = list(map(int, input().split()))		for i in range(T):
			n = int(input())
	~~if n < 1 or n > 1000 or m < 1 or m > 1000:~~		A = list(map(int, input().split()))
	~~print("Datele nu corespund restricțiilor impuse.")~~		m = int(input())
	~~continue~~		B = list(map(int, input().split()))
			if not validare(n, A, m, B):
	if ~~any~~(~~x < 1 or x > 10000 for x in~~ A~~) or any(x < 1 or x > 10000 for x in~~ B):		print("Datele nu corespund restricțiilor impuse.")
	print("Datele nu corespund restricțiilor impuse.")		else:
	~~continue~~		print(se_poate_reduca_la_B(A, B))

	~~if sum(A) != sum(B)~~:
	print(0)
	~~continue~~

	~~if can_reduce~~(A, B):
	~~print(1)~~
	~~else:~~
	~~print(0~~)

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Programul are o singură funcție numită reduce_to_b.~~ Această funcție primește ca ~~argumente~~ două liste a și b, și returnează ~~o valoare de tipul boolean~~, ~~care indică dacă lista a se poate reduce la lista b~~.		validate_data(a, b): Această funcție primește ca parametri două liste, a și b, reprezentând cele două tablouri. Funcția validează dacă datele introduse respectă restricțiile problemei, adică dacă dimensiunile celor două tablouri sunt între 1 și 1000 și dacă toate elementele tablourilor sunt numere naturale între 1 și 10000. Dacă datele sunt valide, funcția returnează True, în caz contrar returnează False.

	În ~~interiorul funcției~~, se parcurge ~~lista~~ b și se caută ~~secvențele din lista~~ a ~~care adunate dau fiecare element din lista b. Pentru aceasta~~, ~~se pornește de la prima poziție din lista~~ a ~~și se adună elementele de la acea poziție până când suma acestora este~~ egală cu ~~primul element~~ din ~~lista~~ b. Dacă ~~s-a găsit~~ o astfel de secvență, se trece la următorul element din ~~lista~~ b ~~și se caută o altă secvență începând de la poziția imediat următoare celei la care s-a găsit ultima secvență~~. Dacă nu ~~s-a găsit nicio~~ secvență ~~care să corespundă elementului curent din lista b~~, funcția returnează False. Dacă s-au ~~găsit secvențe corespunzătoare tuturor elementelor din lista b~~, funcția returnează True.		reduce(a, b): Această funcție primește ca parametri două liste, a și b, reprezentând cele două tablouri. Funcția verifică dacă tabloul a se poate reduce la tabloul b. În acest scop, parcurge fiecare element al tabloului b și caută în tabloul a o secvență de elemente consecutive aflate pe poziții consecutive în tabloul a, a cărei sumă să fie egală cu elementul curent din tabloul b. Dacă găsește o astfel de secvență, o elimină din tabloul a și trece la următorul element din tabloul b. Dacă nu găsește o astfel de secvență, funcția returnează False. Dacă se parcurge cu succes întregul tablou b și toate elementele sale au fost găsite în tabloul a, funcția returnează True.

	În funcția ~~main~~ se ~~face citirea datelor~~ și se ~~apelaează~~ funcția ~~reduce_to_b~~ pentru ~~fiecare set~~ de ~~date~~. ~~În funcție de rezultatul returnat de această funcție,~~ se afișează ~~1 sau 0~~, ~~în funcție de faptul că lista a~~ se ~~poate reduce la lista b sau nu~~.		main(): Această funcție este funcția principală a programului. Ea citeste datele de intrare din consolă, apoi validează datele folosind funcția validate_data. Dacă datele sunt valide, se parcurg cele t teste și pentru fiecare test se citesc cele două tablouri și se apelează funcția reduce pentru a verifica dacă primul tablou se poate reduce la cel de-al doilea. Rezultatul verificării se afișează în consolă. Dacă datele nu sunt valide, se afișează un mesaj corespunzător.

Flaviu at 21:28, 13 May 2023

2023-05-13T21:28:24Z

← Older revision		Revision as of 21:28, 13 May 2023
Line 41:		Line 41:
	; Intrare		; Intrare
	: 2		: 2
	: 12		: 1001
	: 7 3 4 1 6 4 6 9 7 1 8 7		: 7 3 4 1 6 4 6 9 7 1 8 7
	: 4		: 4
Line 58:		Line 58:
	# 0071 - Reducere		# 0071 - Reducere

	def ~~citeste_date_intrare~~():		def can_reduce(A, B):
	n = ~~int(input())~~		n = len(A)
	~~a = list(map(int, input().split~~()))		m = len(B)
	m = ~~int(input())~~
	~~b = list(map(int, input().split~~()))
	~~return a, b~~

	~~def valideaza_datele_intrare(a, b):~~		i = j = 0
	~~if not(0 < len(a)~~ < ~~1001~~ and ~~0 < len(b)~~ < ~~1001)~~:		while i < n and j < m:
	~~return False~~		if A[i] == B[j]:
	~~if not(all(~~1 <= x <= ~~10000 for x in a) and all(~~1 <= ~~x <~~= ~~10000 for x in b))~~:		i += 1
	return False		j += 1
	return ~~True~~		else:
			sum_a = A[i]
			sum_b = B[j]
			while i < n-1 and sum_a != sum_b:
			i += 1
			sum_a += A[i]
			while j < m-1 and sum_a != sum_b:
			j += 1
			sum_b += B[j]
			if sum_a != sum_b:
			return False

			return j == m

	~~def se_poate_reduce(a, b)~~:		if __name__ == "__main__":
	~~i, j~~ = ~~0, 0~~		T = int(input())
	~~while~~ i ~~< len~~(~~a) and j < len(b~~):		for i in range(T):
	s = ~~a[i]~~		n = int(input())
	~~i +~~= 1		A = list(map(int, input().split()))
	~~while i < len~~(a) ~~and s < b[j]:~~		m = int(input())
	~~s +~~= ~~a[i]~~		B = list(map(int, input().split()))
	~~i += 1~~
	if ~~s != b[j]~~:		if n < 1 or n > 1000 or m < 1 or m > 1000:
	~~return False~~		print("Datele nu corespund restricțiilor impuse.")
	~~j += 1~~		continue
	~~return j == len~~(b)

	if ~~__name__ == '__main__':~~		if any(x < 1 or x > 10000 for x in A) or any(x < 1 or x > 10000 for x in B):
	~~t = int~~(~~input())~~
	for _ in ~~range(t~~):
	~~a, b = citeste_date_intrare()~~
	~~if valideaza_datele_intrare(a, b):~~
	~~if se_poate_reduce(a, b):~~
	~~print("Datele sunt introduse corect.")~~
	~~print~~(1)
	~~else:~~
	~~print("Datele sunt introduse corect.")~~
	~~print(0)~~
	~~else~~:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
			continue

			if sum(A) != sum(B):
			print(0)
			continue

			if can_reduce(A, B):
			print(1)
			else:
			print(0)

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Funcția citeste_date_intrare() citește cele~~ două ~~tablouri A~~ și ~~B din intrare~~ și le returnează ca o ~~pereche~~ de ~~liste~~. ~~Funcția valideaza_datele_intrare(~~a, ~~b) verifică dacă cele două liste respectă constrângerile impuse~~ de ~~problemă~~ și ~~returnează True dacă da și False altfel~~. ~~Funcția se_poate_reduce(~~a, b~~) verifică dacă tabloul A~~ se ~~poate reduce~~ la ~~tabloul B și~~ returnează True ~~dacă da și False altfel~~.		Programul are o singură funcție numită reduce_to_b. Această funcție primește ca argumente două liste a și b, și returnează o valoare de tipul boolean, care indică dacă lista a se poate reduce la lista b.

			În interiorul funcției, se parcurge lista b și se caută secvențele din lista a care adunate dau fiecare element din lista b. Pentru aceasta, se pornește de la prima poziție din lista a și se adună elementele de la acea poziție până când suma acestora este egală cu primul element din lista b. Dacă s-a găsit o astfel de secvență, se trece la următorul element din lista b și se caută o altă secvență începând de la poziția imediat următoare celei la care s-a găsit ultima secvență. Dacă nu s-a găsit nicio secvență care să corespundă elementului curent din lista b, funcția returnează False. Dacă s-au găsit secvențe corespunzătoare tuturor elementelor din lista b, funcția returnează True.

	În funcția ~~principală (if __name__ == '__main__':)~~ se ~~citește numărul de seturi de date de test t, apoi~~ se ~~parcurg t iterații~~ pentru ~~a procesa~~ fiecare set de date. ~~Se citesc cele două tablouri~~, se ~~validează și se verifică dacă A~~ se poate reduce la ~~B și se afișează rezultatul~~.		În funcția main se face citirea datelor și se apelaează funcția reduce_to_b pentru fiecare set de date. În funcție de rezultatul returnat de această funcție, se afișează 1 sau 0, în funcție de faptul că lista a se poate reduce la lista b sau nu.

Flaviu at 07:25, 3 May 2023

2023-05-03T07:25:50Z

← Older revision		Revision as of 07:25, 3 May 2023
Line 22:		Line 22:
	* elementele vectorilor A, B sunt numere naturale din intervalul [1,10000]		* elementele vectorilor A, B sunt numere naturale din intervalul [1,10000]
	0 < T ≤ 10		0 < T ≤ 10
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 2		: 2
Line 38:		Line 38:
	: 0		: 0

	== Exemplu ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: 2		: 2

Flaviu at 07:25, 3 May 2023

2023-05-03T07:25:33Z

← Older revision		Revision as of 07:25, 3 May 2023
Line 16:		Line 16:
	== 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 '''afișează pentru fiecare dintre cele T teste, pe câte o linie a ecranului valoare 1, dacă tabloul A se poate reduce la tabloul B''', 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 34:		Line 34:
	: 5 3 4		: 5 3 4
	; Ieșire		; Ieșire
	: Datele ~~nu corespund restricțiilor impuse~~.		: Datele sunt introduse corect.
	: 1		: 1
	: 0		: 0

			== Exemplu ==
			; Intrare
			: 2
			: 12
			: 7 3 4 1 6 4 6 9 7 1 8 7
			: 4
			: 14 7 26 16
			: 5
			: 1 4 2 2 3
			: 3
			: 5 3 4
			; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: 2
			: 3
	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===

Flaviu at 18:17, 27 April 2023

2023-04-27T18:17:12Z

← Older revision		Revision as of 18:17, 27 April 2023
Line 15:		Line 15:

	== Date de ieșire ==		== Date de ieșire ==
	~~Programul afișează pentru fiecare dintre cele T teste~~, pe ~~câte o linie a ecranului valoare 1~~, ~~dacă tabloul A se poate reduce la tabloul B~~, ~~respectiv 0 în caz~~ contrar.		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 33:		Line 34:
	: 5 3 4		: 5 3 4
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: 1		: 1
	: 0		: 0
Line 42:		Line 44:

	def citeste_date_intrare():		def citeste_date_intrare():
	~~"""Functia citeste datele de intrare si returneaza cele doua liste A si B."""~~
	n = int(input())		n = int(input())
	a = [int~~(x) for x in~~ input().split()]		a = list(map(int, input().split()))
	m = int(input())		m = int(input())
	b = [int~~(x) for x in~~ input().split()]		b = list(map(int, input().split()))
	return a, b		return a, b

	def ~~verifica_reducere~~(a, b):		def valideaza_datele_intrare(a, b):
	~~"""Verifica daca lista~~ a ~~se poate reduce la lista~~ b~~."""~~		if not(0 < len(a) < 1001 and 0 < len(b) < 1001):
	j = ~~0 # pozitia curenta~~ in ~~lista~~ a		return False
	for x in b:		if not(all(1 <= x <= 10000 for x in a) and all(1 <= x <= 10000 for x in b)):
	s = ~~0 # suma elementelor consecutive din lista~~ a		return False
	while j < len(a) and s < x:		return True
	s += a[j]
	j += 1		def se_poate_reduce(a, b):
	if s != x:		i, j = 0, 0
			while i < len(a) and j < len(b):
			s = a[i]
			i += 1
			while i < len(a) and s < b[j]:
			s += a[i]
			i += 1
			if s != b[j]:
	return False		return False
	return ~~True~~		j += 1
			return j == len(b)

	if __name__ == '__main__':		if __name__ == '__main__':
	t = int(input()) ~~# numarul de teste~~		t = int(input())
	for i in range(t):		for _ in range(t):
	a, b = citeste_date_intrare()		a, b = citeste_date_intrare()
	if ~~verifica_reducere~~(a, b):		if valideaza_datele_intrare(a, b):
	print(1)		if se_poate_reduce(a, b):
			print("Datele sunt introduse corect.")
			print(1)
			else:
			print("Datele sunt introduse corect.")
			print(0)
	else:		else:
	print(0)		print("Datele nu corespund restricțiilor impuse.")


Line 74:		Line 88:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~În funcția~~ citeste_date_intrare ~~citim numărul de elemente ale fiecărei liste, apoi citim elementele~~ și le ~~returnăm~~ ca o pereche de liste.		Funcția citeste_date_intrare() citește cele două tablouri A și B din intrare și le returnează ca o pereche de liste. Funcția valideaza_datele_intrare(a, b) verifică dacă cele două liste respectă constrângerile impuse de problemă și returnează True dacă da și False altfel. Funcția se_poate_reduce(a, b) verifică dacă tabloul A se poate reduce la tabloul B și returnează True dacă da și False altfel.
	~~În funcția verifica_reducere parcurgem lista~~ b și ~~pentru fiecare element verificăm~~ dacă ~~se poate obține ca sumă a unor elemente consecutive din lista~~ a~~. Pentru aceasta~~, ținem cont de poziția curentă j în lista a și calculăm suma s a elementelor consecutive din această listă începând de la poziția j până când această sumă depășește elementul curent din lista b ~~sau ajungem la sfârșitul listei a. Dacă la sfârșitul verificării suma s nu este egală cu elementul curent din lista b, atunci lista a nu~~ se poate reduce la ~~lista b~~ și ~~funcția~~ returnează False.
	În ~~blocul~~ if __name__ == '__main__' ~~citim~~ numărul de ~~teste~~, apoi ~~citim datele de intrare~~ pentru fiecare ~~test~~ și ~~verificăm~~ dacă ~~lista a~~ se poate reduce la ~~lista b. Rezultatul verificării este afișat pe ecran~~.		În funcția principală (if __name__ == '__main__':) se citește numărul de seturi de date de test t, apoi se parcurg t iterații pentru a procesa fiecare set de date. Se citesc cele două tablouri, se validează și se verifică dacă A se poate reduce la B și se afișează rezultatul.

Flaviu at 19:57, 17 April 2023

2023-04-17T19:57:32Z

← Older revision		Revision as of 19:57, 17 April 2023
Line 41:		Line 41:
	# 0071 - Reducere		# 0071 - Reducere

	~~T = int(input~~())		def citeste_date_intrare():
			"""Functia citeste datele de intrare si returneaza cele doua liste A si B."""
	~~for _ in range(T):~~
	n = int(input())		n = int(input())
	A = ~~list~~(~~map(int,~~ input().split()))		a = [int(x) for x in input().split()]
	m = int(input())		m = int(input())
	B = ~~list~~(~~map(int,~~ input().split()))		b = [int(x) for x in input().split()]
			return a, b

	~~i =~~ j = 0		def verifica_reducere(a, b):
	~~while i < n and j < m~~:		"""Verifica daca lista a se poate reduce la lista b."""
	~~sum~~ = 0		j = 0 # pozitia curenta in lista a
	while j < m and ~~sum~~ < ~~A[i]~~:		for x in b:
	~~sum~~ += B[j]		s = 0 # suma elementelor consecutive din lista a
			while j < len(a) and s < x:
			s += a[j]
	j += 1		j += 1
	if ~~sum~~ != ~~A[i]~~:		if s != x:
	~~break~~		return False
	~~i +~~= 1		return True
	if i =~~= n~~:
	print(1)		if __name__ == '__main__':
	else:		t = int(input()) # numarul de teste
	print(0)		for i in range(t):
			a, b = citeste_date_intrare()
			if verifica_reducere(a, b):
			print(1)
			else:
			print(0)


	</syntaxhighlight>		</syntaxhighlight>
			== Explicatie Rezolvare ==

			În funcția citeste_date_intrare citim numărul de elemente ale fiecărei liste, apoi citim elementele și le returnăm ca o pereche de liste.
			În funcția verifica_reducere parcurgem lista b și pentru fiecare element verificăm dacă se poate obține ca sumă a unor elemente consecutive din lista a. Pentru aceasta, ținem cont de poziția curentă j în lista a și calculăm suma s a elementelor consecutive din această listă începând de la poziția j până când această sumă depășește elementul curent din lista b sau ajungem la sfârșitul listei a. Dacă la sfârșitul verificării suma s nu este egală cu elementul curent din lista b, atunci lista a nu se poate reduce la lista b și funcția returnează False.
			În blocul if __name__ == '__main__' citim numărul de teste, apoi citim datele de intrare pentru fiecare test și verificăm dacă lista a se poate reduce la lista b. Rezultatul verificării este afișat pe ecran.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0071 - Reducere] ---- == Cerinţa == Se consideră două tablouri unidimensionale A și B cu elemente numere naturale din intervalul [1,10000]. Spunem că tabloul A se poate reduce la tabloul B dacă există o împărțire a tabloului A în secvențe disjuncte de elemente aflate pe poziţii consecutive în tabloul A astfel încât prin înlocuirea secvențelor cu suma elementelor din secvență să se obţină, în ordine, el...

2023-03-21T21:33:02Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0071 - Reducere] ---- == Cerinţa == Se consideră două tablouri unidimensionale A și B cu elemente numere naturale din intervalul [1,10000]. Spunem că tabloul A se poate reduce la tabloul B dacă există o împărțire a tabloului A în secvențe disjuncte de elemente aflate pe poziţii consecutive în tabloul A astfel încât prin înlocuirea secvențelor cu suma elementelor din secvență să se obţină, în ordine, el...

New page

Sursa: [https://www.pbinfo.ro/probleme/71/reducere 0071 - Reducere]
----
== Cerinţa ==
Se consideră două tablouri unidimensionale A și B cu elemente numere naturale din intervalul [1,10000]. Spunem că tabloul A se poate reduce la tabloul B dacă există o împărțire a tabloului A în secvențe disjuncte de elemente aflate pe poziţii consecutive în tabloul A astfel încât prin înlocuirea secvențelor cu suma elementelor din secvență să se obţină, în ordine, elementele tabloului B.
Se dau două tablouri A și B. Să se verifice dacă tabloul A se poate reduce la tabloul B.

Programul va citi mai multe seturi de date, fiecare constând în doi vectori A, B și va afișa pentru fiecare set de date dacă tabloul A se poate reduce la tabloul B.
== Date de intrare ==
Programul citește un număr natural T, reprezentând numărul de seturi de date de test care urmează. Urmează T seturi de date, descrise astfel:

* se citește n
* se citesc n valori, reprezentând elementele tabloului A
* se citește m
* se citesc m valori, reprezentând elementele tabloului B

== Date de ieșire ==
Programul afișează pentru fiecare dintre cele T teste, pe câte o linie a ecranului valoare 1, dacă tabloul A se poate reduce la tabloul B, respectiv 0 în caz contrar.

== Restricţii şi precizări ==
* 0 < n, m < 1001
* elementele vectorilor A, B sunt numere naturale din intervalul [1,10000]
0 < T ≤ 10
== Exemplu ==
; Intrare
: 2
: 12
: 7 3 4 1 6 4 6 9 7 1 8 7
: 4
: 14 7 26 16
: 5
: 1 4 2 2 3
: 3
: 5 3 4
; Ieșire
: 1
: 0

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0071 - Reducere

T = int(input())

for _ in range(T):
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

i = j = 0
while i < n and j < m:
sum = 0
while j < m and sum < A[i]:
sum += B[j]
j += 1
if sum != A[i]:
break
i += 1
if i == n:
print(1)
else:
print(0)

</syntaxhighlight>