Se citesc m tipuri de monede (valori date, disponibile in cantitate nelimitata) si o suma S. Determinati, folosind Programarea Dinamica, in cate moduri distincte se poate obtine suma S folosind aceste monede, ORDINEA in care sunt folosite monedele nefiind relevanta (doua moduri care folosesc aceleasi cantitati din fiecare tip de moneda sunt considerate identice).
- Date de intrare
- Pe prima linie se citesc m si S. Pe a doua linie se citesc cele m valori ale monedelor.
- Date de iesire
- Se afiseaza un singur numar: numarul de moduri de a obtine suma S.
- Restrictii
- 1 <= m <= 100, 0 <= S <= 10000, 1 <= valoare moneda <= 10000
Exemple
Exemplul 1
Intrare
3 4 1 2 3
Iesire
4
Exemplul 2
Intrare
2 5 1 2
Iesire
3