Payment

题目描述

在 AtCoder 王国，只有纸币被用作货币。有 $10^{100}+1$ 种面额的纸币，面值为 $1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}$。你在商场购物，现在要购买一台价值为 $N$ 的章鱼烧机。（章鱼烧是日本小吃的名称。） 为了付款，你会选择一些不小于 $N$ 的金额并交给店员。然后，店员找给你的零钱等于你付的金额减去 $N$。 当你和店员都选择能使纸币总数最小的纸币组合时，总共使用的纸币数的最小可能值是多少？ 假设你和店员都有充足数量的纸币。

输入格式

输入按标准输入给出，格式如下： $N$

输出格式

输出最小可能使用的纸币总数。

36

8

91

3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

243

提示

$N$ 是一个在 $1$ 到 $10^{1,000,000}$（含）之间的整数。如果你给出四张面值为 $10$ 的纸币，而店员找给你四张面值为 $1$ 的纸币，则总共使用了八张纸币。 不能用少于八张纸币完成付款，所以答案是 $8$.
如果你给出两张面值为 $100, 1$ 的纸币，而店员找给你一张面值为 $10$ 的纸币，则总共使用了三张纸币。

标签: AtCoder|abc155E

来源

AtCoder|abc155E