atcoder#AGC011E. [AGC011E] Increasing Numbers

[AGC011E] Increasing Numbers

题目描述

10 進法で表記したとき,桁同士が隣り合っているところではすべて,右にある桁の値のほうが左にある桁の値以上であるような 0 0 以上の整数を,増加的と呼ぶことにします. たとえば,1558 1558 11 11 3 3 0 0 は増加的ですが,10 10 20170312 20170312 は増加的ではありません.

すぬけ君は,整数 N N を持っています. N N が最小で何個の増加的な数の和として表されるかを求めてください.

输入格式

入力は以下の形式で標準入力から与えられる。

N N

输出格式

N N が最小で何個の増加的な数の和として表されるかを出力せよ.

题目大意

我们说一个数是“递增的”,当且仅当对于它的任意相邻的两位都有左边小于等于右边。
15581558, 1111, 33 是递增的,20170312201703121926081719260817 就不是。
现在给你一个数 nn,问最少可以被表示成几个递增的数之和。
比如 80=56+2480 = 56 + 242017=1349+6682017 = 1349 + 668, 2019=1669+237+1132019 = 1669 + 237 + 113

1n105000001 ≤ n ≤ 10^{500000}

80
2
123456789
1
20170312
4
7204647845201772120166980358816078279571541735614841625060678056933503
31

提示

制約

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

Sample Explanation 1

例えば,80 = 77 + 3 80\ =\ 77\ +\ 3 として表すことができます.

Sample Explanation 2

123456789 123456789 はそれ自体が増加的なので,1 1 個の増加的な数の和で表すことができます.