# PBinfo #4186 – Monede – Rezolvare C++

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

## Enunț

Cerința
Se dau n numere naturale reprezentând valorile unor monede și S reprezentând o sumă de bani. Să se afișeze numărul de modalități de a plăti suma cu cele n valori. 

Date de intrare
Programul citește de la tastatură numărul S, apoi numărul n, iar apoi n numere naturale, separate prin spații reprezentând valorile celor n monede.

Date de ieșire
Programul va afișa pe ecran numărul m, reprezentând numărul de modalități de a plăti suma S.

Restricții și precizări

1≤ S ≤ 250
1 ≤ n ≤ 100
cele n numere citite sunt distincte și vor fi mai mici decât 100

Exemplu:
Intrare

4 3
1 2 3
Ieșire

4
Explicație
Sunt 4 modalităti de a plăti suma 4:
{1,1,1,1}
{1,1,2}
{1,3}
{2,2}

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
long Monede(int s, vector<long> c)
{
    int l=c.size();
    long x;
    vector<long>ar;
    for(int i=0; i<=s; i++)
        ar.push_back(0);
    ar[0]=1;
    for(int i=0; i<l; i++)
    {
        x=c[i];
        for(int j=x; j<=s; j++)
        {
            if(ar[j-x]!=0)ar[j]+=ar[j-x];
        }
    }
    return ar[s];
}
int main()
{
    int n,s,i,x;
    cin>>s>>n;
    vector<long> c;
    for(i=0; i<n; i++)
    {
        cin>>x;
        c.push_back(x);
    }
    cout<<Monede(s, c);
    return 0;
}
```

## Resurse

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