==Include(page="template/taskheader" task_id="monezi")==
==Include(page="template/taskheader" task_id="monezi")==
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. 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 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. 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
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/raw")==
monezi
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. 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 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. 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|Explicatii |
|2 10 |17 |Cu subsetul {2} se pot obtine 5 sume: 2, 4, 6, 8, 10 |
| | | |
|2 | |Cu subsetul {3} se pot obtine 3 sume: 3, 6, 9 |
| | | |
|3 | |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")==
