atcoder#AGC011E. [AGC011E] Increasing Numbers

[AGC011E] Increasing Numbers

配点 : 13001300

問題文

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

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

制約

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

入力

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

NN

出力

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

80
2

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

123456789
1

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

20170312
4
7204647845201772120166980358816078279571541735614841625060678056933503
31