← 返回题目列表

AtCoder · abc155_e

E. 付款

中文机器翻译题面 查看原题

分数: 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