Se citeste o suma naturala S. Folosind sistemul canonic de monede cu valorile 1, 2, 5, 10, 20, 50, 100, 200 si 500 (fiecare valoare disponibila in cantitate nelimitata), determinati, folosind metoda Greedy, numarul minim de monede necesare pentru a obtine exact suma S.
- Date de intrare
- Se citeste numarul natural S.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de monede necesare.
- Restrictii
- 0 <= S <= 10^9
Exemple
Exemplul 1
Intrare
0
Iesire
0
Exemplul 2
Intrare
1
Iesire
1