Î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 |