0071 - Reducere
Sursa: 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>