0071 - Reducere

De la Universitas MediaWiki
Versiunea din 21 martie 2023 21:33, autor: Flaviu (discuție | contribuții) (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...)
(dif) ← Versiunea anterioară | Versiunea curentă (dif) | Versiunea următoare → (dif)

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

# 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)