No.636 Number of Coins 2
しらっ亭
はむこProblem Statement
In the country of YUKI, for every non-negative integer $k$, coins with denominations of $1 \times 10^k$ yen and $5 \times 10^k$ yen are in circulation.
Listing some of the coins in circulation in ascending order of denomination gives $1, 5, 10, 50, 100, 500, \dots $.
Yukiko wants to buy an item costing $N$ yen at a store.
To settle the payment of $N$ yen, she pays the store $X (X \ge N)$ yen in YUKI coins and receives $X-N$ yen in YUKI coins as change.
Both when paying coins and when receiving them as change, the coins exchanged are chosen so that their number is minimized.
Both Yukiko and the store have $10^{10000}$ coins of every denomination, so they never run short of coins during the exchange.
Yukiko wants to minimize the number of coins exchanged, that is, "the sum of the number of coins she gives and the number of coins she receives".
Find the minimum number of coins exchanged.
Input
N
$1 \le N \le 10^{10000}$
$N$ is an integer.
Note that $N$ may not fit in a 32-bit or 64-bit integer type.
Output
Output the answer on a single line. Print a newline at the end.
Sample
Sample 1
Input
87
Output
5
For example, to settle a payment of $87$ yen, she gives $102$ yen and receives $15$ yen.
By giving $3$ coins of denominations $100, 1, 1$ and receiving $2$ coins of denominations $10, 5$, the number of coins exchanged is $5$, which is the minimum.
Sample 2
Input
1343414
Output
11
For example, she gives $1500015$ yen and receives $156601$ yen. With $4$ coins given and $7$ coins received, a total of $11$ coins are exchanged, which is the minimum.
Sample 3
Input
175
Output
5
She can either pay $100, 50, 10, 10, 5$ and receive no change, or pay $100, 100$ and receive $10, 10, 5$ as change. Both ways exchange $5$ coins, which is the minimum.
Sample 4
Input
5000000000000000
Output
1
The payment can be made with $1$ coin.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。