#P12925. [AGC011E] Increasing Numbers

    ID: 12109 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-暴力枚举高精度乘法高精度加法增量维护势能分析同余的加减乘运算

[AGC011E] Increasing Numbers

题目描述

当用十进制表示一个整数时,如果所有相邻的数位都满足右边的数位数值不少于左边的数位数值,我们称这样的非负整数为“递增数”。例如,15581558、1111、33、00 是递增数,而 1010 和 2017031220170312 不是递增数。

すぬけ君有一个整数 NN。请计算,将 NN 表示为若干个递增数之和,最少需要几个递增数。

输入格式

输入为一行,包含一个整数 NN。

输出格式

输出仅一行,表示将 NN 表示为若干个递增数的和时,所需递增数的最小个数。

输入输出样例 #1

输入 #1

80

输出 #1

2

输入输出样例 #2

输入 #2

123456789

输出 #2

1

输入输出样例 #3

输入 #3

20170312

输出 #3

4

输入输出样例 #4

输入 #4

7204647845201772120166980358816078279571541735614841625060678056933503

输出 #4

31

说明/提示

限制

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

样例解释 1

例如,80=77+380 = 77 + 3,可以表示为两个递增数之和。

样例解释 2

123456789123456789 本身就是递增数,所以只需要 11 个递增数即可表示。