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.

Cerinţa

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

Explicație

Pentru primul set de date, 7+3+4=14, 1+6=7, 4+6+9+7=26, 1+8+7=16, deci tabloul A se poate reduce la B.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0 ; i < t ; ++i)
    {
        int n , m;
        int a[1001] , b[1001];
        cin >> n;
        for(int j = 0 ; j < n ; ++j)
        cin >> a[j];
        cin >> m;
        for(int j = 0 ; j < m ; ++j)
        cin >> b[j];
        int cnt=0;
        int ok=0;
        for(int j = 0 ; j < m ; ++j)
        {
            int s=0;
            for(int k = ok ; k < n ; ++k)
            {
                s+=a[k];
                ok++;
                if(s >= b[j])
                break;
            }
            if(b[j]==s)
            cnt++;
        }
        if(cnt==m && ok==n)
        cout << 1 << endl;
        else
        cout << 0 << endl;
    }
}