Rezolvare PBinfo #3170

Cerința

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, știind că se pot folosi oricâte bancnote de orice tip.

Date de intrare

Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor.

Date de ieșire

Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.

Restricții și precizări

• 1 ≤ n ≤ 6
• 1 ≤ S ≤ 1000
• 1 ≤ v[i] ≤ 100
• oricare variantă corectă de plată a sumei S va fi luată în considerare
• pentru toate seturile de date există soluție

Exemplu:

Intrare

5 375
1 5 10 50 100

Ieșire

5 2 1 1 3 

Observații

Există și alte soluții valide.