分数: 500 点
问题陈述
在AtCoder王国,仅使用纸币作为货币。有 10^{100}+1 种纸币,面值为 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}。您来到商场购物,现在购买一台章鱼烧机,价值为 N. (章鱼烧是一种日本小吃的名称。)
为了付款,您将选择一定金额,该金额至少为 N 并将其交给店员。然后,店员把零钱还给你,就是你给的钱减去零钱 N.
当您和店员都选择纸币组合来最小化纸币数量时,您和店员使用的纸币总数最少可能是多少?
假设你有足够数量的钞票,店员也有足够数量的钞票。
约束
- N 是介于 1 和 10^{1,000,000} (含)。
输入
输入由标准输入按以下格式给出:
N
输出
打印您和店员可能使用的最少纸币总数。
示例输入 1
36
示例输出 1
8
如果你给四张有价钞票 10 每张,店员还给你四张等价钞票 1 每张,总共使用了八张钞票。
总共少于八张钞票无法付款,所以答案是 8.
示例输入 2
91
示例输出 2
3
如果您给予两张有价纸币 100, 1,店员还给你一张有价的钞票 10,一共使用了三张钞票。
示例输入 3
314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170
示例输出 3
243