#P1511. [SDOI2006] 数字串位置 / 超长数字串

[SDOI2006] 数字串位置 / 超长数字串

题目背景

George 很喜欢数学,尤其是算数数系列。

题目描述

他最喜欢的是数字的无穷序列,结果是把所有的自然数按升序排列。这个序列开始是:1234567891011121314...\texttt{1234567891011121314...}

我们称这个序列为序列 SS,然后 S1=1S_1 = 1, S2=2S_2 = 2, ... , S10=1S_{10} = 1, S11=0S_{11} = 0,依此类推.

George 现有一个数字序列 AA ,他想知道这个序列在 SS 中最早出现的位置。请你帮助他解决这个问题。

输入格式

输入一个字符串,表示数字序列 AA ,位数不超过 200200,中间没有空格。

输出格式

输出使 $A_1 = S_k, A_2 = S_{k+1}, ...,A_{len_{A}} = S_{k + len(A)-1}$ 成立的最小正整数 kk,其中 lenAlen_{A} 表示序列 AA 的长度。

101

10

提示

来源 Source

Ural State University Problem Archive