Rendu de monnaie optimal

Il n'y a rien de plus énervant, lorsqu'on fait un achat avec un billet, de se retrouver avec des dizaines de pièces de monnaie ! Malheureusement, le système monétaire sur Algoréa n'est pas des plus pratiques. Il y a en effet un billet de 1000 écus puis des pièces de 5, 2 et 1 écus. Vous pouvez imaginer à quel point on peut se retrouver avec beaucoup de pièces !

Les commerçants essaient cependant de toujours rendre, pour une somme donnée, un nombre de pièces minimum. Vous devez les aider.

Ce que doit faire votre programme :

Vous devrez lire un entier, la somme à rendre, et vous devez calculer et afficher le nombre de pièces de 5, 2 et 1 écus à rendre afin que le nombre total de pièces soit le plus petit possible.

Exemples

Exemple 1

entrée :

8

sortie :

1
1
1

Exemple 2

entrée :

421

sortie :

84
0
1

Exemple 3

entrée :

42

sortie :

8
1
0

Source : http://www.france-ioi.org/