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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Reducere:

#include <iostream>
using namespace std;

int T, n, m, a[1001], b[1001];

int main(){
    cin >> T;
    for( ; T ; --T) // pentru fiecare test
    {
        // citim cei doi vectori
        cin >> n;
        for(int i=1;i<=n;++i)
            cin >> a[i];
        cin >> m;
        for(int i = 1;i <=m ; ++i)
            cin >> b[i];
        // incercam sa scriem fiecare element din b[] ca suma de elemente consecutive din a[]
        // daca reusim, a[] se reduce la b[]
        // daca ceva nu merege bine, a[] nu se reduce la b[]
        // practic trebuie sa gasim in a[] m secvente disjuncte, care sa contina toate elementele din a[] si
        // elementele din prima secventa sa dea suma b[1]
        // elementele din a doua secventa sa dea suma b[2]
        // etc.
        int k = 1;
        int ok = 1;
        for(int i = 1 ; i <= n && ok ; ++i){
            if(a[i] <= b[k])
            {
                b[k] -= a[i];
                if(b[k] == 0)
                    k++;
            }
            else
                ok = 0;

        }
        if(k != m + 1)
            ok = 0;
        cout << ok << endl;
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #71 Reducere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #71 Reducere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #71 Reducere