Fişierul intrare/ieşire:monezi.in, monezi.outSursăStelele Informaticii 2005, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Cerinta

Calculati pentru Algorel suma capacitatilor de acoperire a tuturor subseturilor de tipuri de monede din trezoreria sa (in total sunt 2N-1 seturi posibile). Numai dupa ce afla raspunsul la problema aceasta Algorel se poate ocupa de eliberarea printesei.

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.

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.

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

Exemplu

monezi.inmonezi.out
2 10
2
3
17

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content