În urma reformei monetare finanţiştii au ajuns la concluzia că numărul de valori monetare necesar pentru plata oricărei sume este 4 şi le-au numit, pentru simplitate RAN, REN, RIN, RON. Astfel ei au stabilit ca monedă de bază moneda numită RAN, cu valoarea . Celelalte trei valori le-au exprimat fie în funcţie de moneda de bază, fie în funcţie de altă valoare. Astfel, moneda REN are o valoare de RAN, moneda RIN are valoarea de REN iar moneda RON valoarea de RIN. Finanţiştii îşi pun însă problema dacă cele patru valori monetare oferă o suficientă diversitate de plată astfel încât o sumă de bani să poată fi plătită în mai multe moduri.
Cerință
Scrieţi un program care să determine în câte moduri poate fi plătită o anumită sumă , exprimată în moneda de bază RAN, utilizând noile monede introduse de reforma monetară.
Date de intrare
Fişierul de intrare reforma.in conţine pe prima linie valoarea .
Date de ieșire
Fişierul de ieşire reforma.out conţine pe prima linie un număr natural care indică în câte moduri poate fi plătită suma utilizând noile valori.
Restricții și precizări
Exemplul 1
reforma.in
23
reforma.out
10
Explicație
| # | RAN | REN | RIN | RON |
|---|---|---|---|---|
| 1 | 23 | 0 | 0 | 0 |
| 2 | 18 | 1 | 0 | 0 |
| 3 | 13 | 2 | 0 | 0 |
| 4 | 8 | 3 | 0 | 0 |
| 5 | 3 | 4 | 0 | 0 |
| 6 | 13 | 0 | 1 | 0 |
| 7 | 8 | 1 | 1 | 0 |
| 8 | 3 | 2 | 1 | 0 |
| 9 | 3 | 0 | 2 | 0 |
| 10 | 3 | 0 | 0 | 1 |
Exemplul 2
reforma.in
36
reforma.out
26
Explicație
| # | RAN | REN | RIN | RON |
|---|---|---|---|---|
| 1 | 36 | 0 | 0 | 0 |
| 2 | 31 | 1 | 0 | 0 |
| 3 | 26 | 2 | 0 | 0 |
| 4 | 21 | 3 | 0 | 0 |
| 5 | 16 | 4 | 0 | 0 |
| 6 | 11 | 5 | 0 | 0 |
| 7 | 6 | 6 | 0 | 0 |
| 8 | 1 | 7 | 0 | 0 |
| 9 | 26 | 0 | 1 | 0 |
| 10 | 21 | 1 | 1 | 0 |
| 11 | 16 | 2 | 1 | 0 |
| 12 | 11 | 3 | 1 | 0 |
| 13 | 6 | 4 | 1 | 0 |
| 14 | 1 | 5 | 1 | 0 |
| 15 | 16 | 0 | 2 | 0 |
| 16 | 11 | 1 | 2 | 0 |
| 17 | 6 | 2 | 2 | 0 |
| 18 | 1 | 3 | 2 | 0 |
| 19 | 6 | 0 | 3 | 0 |
| 20 | 1 | 1 | 3 | 0 |
| 21 | 16 | 0 | 0 | 1 |
| 22 | 11 | 1 | 0 | 1 |
| 23 | 6 | 2 | 0 | 1 |
| 24 | 1 | 3 | 0 | 1 |
| 25 | 6 | 0 | 1 | 1 |
| 26 | 1 | 1 | 1 | 1 |