== include(page="template/taskheader" task_id="monezi") ==
==Include(page="template/taskheader" task_id="monezi")==
Poveste ...
Printul Algorel are in trezoreria castelului $N$ tipuri de monezi de aur. Pentru fiecare tip se stie valoarea monezilor de tipul respectiv. Averea printului este imensa, deci se poate considera ca are un numar infinit de monezi de fiecare tip. Pentru a elibera printesa din mainile spanului cel lacom el nu trebuie sa faca vreun act de vitejie ci doar sa-i dea spanului monezi cu valoarea totala $S$. Desi doreste sa-si vada printesa cat mai repede, Algorel incepe sa se gandeasca la tot felul de probleme legate de trezoreria lui. De exemplu, el defineste pentru un subset de tipuri de monede, sa-l numim $X$, capacitatea de acoperire a acestuia ca fiind numarul de sume cuprinse intre $1$ si $S$ (inclusiv) pe care le poate obtine folosind numai monede de tipuri aflate in subsetul $X$. De la acest gand si pana la a calcula suma capacitatilor de acoperire a tutoror subseturilor de monede posibile nu a mai fost decat un pas.
h2. Cerinta
...
Calculati pentru Algorel suma capacitatilor de acoperire a tuturor subseturilor de tipuri de monede din trezoreria sa (in total sunt $2^N^-1$ seturi posibile). Numai dupa ce afla raspunsul la problema aceasta Algorel se poate ocupa de eliberarea printesei.
h2. Restrictii
h2. Date de Intrare
...
Prima linie a fisierului $monezi.in$ contine doua numere intregi separate printr-un spatiu, $N$ si $S$, reprezentand numarul de tipuri de monezi si suma ce trebuie platita spanului. Urmatoarele $N$ linii contin cate un numar intreg, $V[i]$, reprezintand valoarea unei monezi din tipul $i$.
h2. Date de intrare
h2. Date de Iesire
...
Fisierul de iesire $monezi.out$ va contine numarul pe care Algorel vrea sa-l afle, reprezentand suma capacitatilor de acoperire a tuturor subseturile de monede din trezoreria sa.
h2. Date de iesire
h2. Restrictii si precizari
...
* $1 ≤ N ≤ 17$
* $1 ≤ S ≤ 512$
* Valorile monezilor vor fi numere naturale intre $1$ si $500$
* Nu vor exista doua tipuri de monezi cu aceeasi valoare
* Se pot utiliza mai multe monezi de acelasi tip
* Pentru $50%$ din teste $N ≤ 10$
h2. Exemplu
| monezi.in | monezi.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. monezi.in |_. monezi.out |
| 2 10
2
3
| 17 |
h3. Explicatii
Cu subsetul {2} se pot obtine 5 sume: 2, 4, 6, 8, 10
Cu subsetul {3} se pot obtine 3 sume: 3, 6, 9
Cu subsetul {2,3} se pot obtine 9 sume: 2, 3, 4, 5, 6, 7, 8, 9, 10
Observati ca nu e obligatoriu ca toate tipurile de moneda dintr-un subset sa fie folosite: de exemplu suma 6 pentru ultimul subset se obtine folosind numai monede de tip “2” sau numai monede de tip “3” (daca le folosim pe amandoua nu putem obtine suma 6).
Numarul cautat de Algorel va fi astfel 5+3+9=17.
==Include(page="template/taskfooter" task_id="monezi")==
== include(page="template/taskfooter" task_id="monezi") ==
