Problem B
The Bus Card
Languages
en
sv
You are going to purchase a bus card. It’s a refillable card that cash can be deposited into, and then used to ride the bus until you are out of money. You know that you’re planning to travel for $K$ Swedish crowns (SEK). Charging the card takes some time since you can only charge it with $100$, $200$ or $500$ SEK at a time.
At the moment you are in a hurry, so you want to make as few transactions as possible, but never insert more money than necessary. If you are to travel for $800$ SEK, this means you should load it with $500$, then $200$, and then $100$ SEK. On the other hand, if you are traveling for $850$ SEK you should load it first with $500$, and then $200$ SEK twice. $50$ SEK will be wasted, but it’s still the best alternative.
Compute the minimum number of transactions necessary.
Input
The input consists of the integer $K$ ($1 \le K \le 10\, 000$), the amount you will travel for.
Output
Print a single integer: the number of transactions necessary.
Scoring
Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.
|
Group |
Point value |
Constraints |
|
$1$ |
$33$ |
you will never have to insert more money than the amount you travel for. |
|
$2$ |
$67$ |
No additional constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
850 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1800 |
5 |
