Träningstävling finalen 2016


2016-02-05 14:10 CET

Träningstävling finalen 2016


2016-02-05 16:10 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -2602 days 8:49:06

Time elapsed


Time remaining


Problem A
Bus Card

You are buying a transit bus card. It is a reloadable card that you can charge with cash. Afterwards, you can use it until it runs out of money.

You know that you are supposed to make trips for $K$ dollars, where $K \leq 10\, 000$. Charging the card takes some time, since you can only charge it with $500$, $200$ or $100$ dollars at a time. Since you are in a hurry, you want to charge it as few times as possible, but never with more money than necessary.

If you want to travel for $800$ dollars, you want to charge the card first with $500$ dollars, then $200$ dollars and finally with $100$ dollars. If you want to travel for $850$ dollars, you first need to charge it with $500$ dollars and then charge it with $200$ dollars twice. You will waste $50$ dollars, but it is still the best alternative (you cannot waste less).

Write a program that computes the least number of times you need to charge the card.


The input contains an integer $1 \le K \le 10\, 000$, the number of dollars you want to charge the card with.


Your program should output a single integer; the least number of transactions you need to do.


Your program will be tested on three test cases. If you pass two of them, you get $50$ points. If you pass three of them, you get $100$ points.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2