# PBinfo #1924 – QStiva – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă o stivă inițial vidă. Să se efectueze Q operații de forma:

1 x: Se adaugă x în stivă.
2: Se șterge elementul din vârful stivei.
3 S: Se întreabă dacă se poate scrie valoarea S ca sumă de elemente aflate în stivă. Fiecare element poate fi folosit o singură dată în calcularea sumei. Răspunsul va fi 1 în caz afirmativ și 0 în caz negativ.

Date de intrare
Fișierul de intrare qstiva.in conține pe prima linie numărul Q, iar pe următoarele Q linii se vor afla operațiile descrise mai sus.

Date de ieșire
Fișierul de ieșire qstiva.out va conține răspunsurile operațiilor de tipul 3, câte un răspuns pe linie, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

1 ≤ Q ≤ 100000
pentru o operație de tipul 1, 1 ≤ x ≤ 1000
pentru o operație de tipul 3, 1 ≤ S ≤ 1000
nu se vor efectua operații de tipul 2 sau de tipul 3 dacă stiva este goală.

Exemplu:
qstiva.in

8
1 12
2
1 1
3 2
1 2
1 12
3 13
2
qstiva.out

0
1

## Cod sursă C++

```cpp
// Popa Bogdan Ioan, Colegiul National Aurel Vlaicu Orastie, clasa a 10-a
#include <bits/stdc++.h>
#define nmax 100001
#define Smax 1000
using namespace std;
ifstream fin("qstiva.in");
ofstream fout("qstiva.out");
int n,x,i,t,Q,j;
bitset <Smax+2> dp[nmax];
int main()
{
    dp[0][0]=1;
    for(fin>>Q;Q;Q--)
    {
        fin>>t;
        if(t==1)
        {
            fin>>x;
            n++;
            dp[n].reset();
            for(i=Smax-x+1;i<=Smax;i++)
                dp[n][i]=dp[n-1][i];
            for(i=Smax-x;i>=0;i--)
                if(dp[n-1][i])
                    dp[n][i+x]=dp[n][i]=1;
        }
        if(t==2)
            n--;
        if(t==3)
        {
            fin>>x;
            fout<<dp[n][x]<<"\n";
        }
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1924)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1924/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1924/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)