問題一覧 > 通常問題

No.636 硬貨の枚数2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 38
作問者 : しらっ亭しらっ亭 / テスター : はむこはむこ
1 ProblemId : 1702 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-01-19 00:31:47

問題文

YUKI国には、任意の非負整数 $k$ に対して、額面が $1 \times 10^k$ 円と $5 \times 10^k$ 円であるような硬貨が流通しています。
流通している硬貨を額面を小さい方からいくつか列挙すると、$1, 5, 10, 50, 100, 500, \dots $ です。

雪子さんは、お店で $N$ 円の品物を購入しようと思っています。
$N$ 円の決済をするのに、YUKI国の硬貨で $X (X \ge N)$ 円をお店に支払い、お釣りとしてYUKI国の硬貨で $X-N$ 円を受け取ります。
決済で硬貨を支払うときも、お釣りとして受け取るときも、枚数が最小となるように硬貨を選んでやり取りを行います。

雪子さんもお店も、全ての額面の硬貨を $10^{10000}$ 枚持っているため、やり取りのときに硬貨が不足してしまうことはありません。

雪子さんは、やり取りする硬貨の枚数、つまり、"渡す硬貨の枚数と受け取る硬貨の枚数の和" を最小化したいです。
やり取りする硬貨の枚数の最小値を求めてください。

入力

N

$1 \le N \le 10^{10000}$
$N$ は整数。
$N$ は 32bit 整数型や 64bit 整数型に収まらない可能性がある点に注意してください。

出力

答えを1行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
87
出力
5

例えば、$87$ 円の決済に、$102$ 円を渡して $15$ 円を受け取ります。
額面 $100, 1, 1$ の $3$ 枚の硬貨を渡し、額面 $10, 5$ の $2$ 枚を受け取ることで、やり取りする硬貨の枚数は $5$ 枚となり、これが最小です。

サンプル2
入力
1343414
出力
11

例えば、$1500015$ 円を渡し、$156601$ 円を受け取ります。渡す硬貨 $4$ 枚と受け取る硬貨 $7$ 枚で合計 $11$ 枚のやり取りとなり、これが最小です。

サンプル3
入力
175
出力
5

$100, 50, 10, 10, 5$ と支払ってお釣りをゼロにする方法と、$100, 100$ と支払ってお釣りを $10, 10, 5$ にする方法があり、いずれも $5$ 枚のやり取りとなり、これが最小です。

サンプル4
入力
5000000000000000
出力
1

5000兆円硬貨 $1$ 枚で支払いが可能です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。