← 返回题目列表

AtCoder · agc011_e

E. 数量不断增加

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

分数: 1300 点

问题陈述

我们将调用一个非负整数 增加 如果对于其十进制表示形式中的任何两个相邻数字,右侧的数字大于或等于左侧的数字。 例如, 1558, 11, 3 和 0 都在增加; 10 和 20170312 不是。

Snuke 有一个整数 N。找出可以表示的最小递增整数数 N 作为它们的总和。

约束

  • 1 \leq N \leq 10^{500000}

输入

输入由标准输入按以下格式给出:

N

输出

打印可以表示的最小递增整数数 N 作为它们的总和。


示例输入 1

80

示例输出 1

2

一种可能的表示是 80 = 77 + 3.


示例输入 2

123456789

示例输出 2

1

123456789 本身是递增的,因此它可以表示为一个递增整数的总和。


示例输入 3

20170312

示例输出 3

4

示例输入 4

7204647845201772120166980358816078279571541735614841625060678056933503

示例输出 4

31