Problem:


Problem D: Revenge of Champernowne Constant

Champernowne constant is an irrational number. Its decimal representation starts with "0.", followed by concatenation of all positive integers in the increasing order.

You will be given a sequence S which consists of decimal digits. Your task is to write a program which computes the position of the first occurrence of S in Champernowne constant after the decimal point.

Input

The input has multiple test cases. Each line of the input has one digit sequence. The input is terminated by a line consisting only of #.

It is guaranteed that each sequence has at least one digit and its length is less than or equal to 100.

Output

For each sequence, output one decimal integer described above. You can assume each output value is less than 1016.

Sample Input

45678
67891011
21
314159265358979
#

Output for the Sample Input

4
6
15
2012778692735799



Sample input:
45678
67891011
21
314159265358979
#


Sample output:
4
6
15
2012778692735799

Submission status: Runtime Error

Solution code:
# ???????????????????°?? ???????????´?????°??????????????????
#?????????????? ?±???????????????????? ???????????????? ???????????´?????°??????????????????, ???±???°???????°???????? ?????????????°???????? ???????????´?????°?????????????? ?????????¶???????????????? ??????????:
# S = 123456789101112131415...
#?????????´?????????? ???????????? ???????¶?´???????? ???°?´?°???????? ?????´???????????´?????°?????????????????? A ?? ?±???????????????????? ???????????´?????°?????????????????? S (???????????°?????? ???°???????°???????? ?? 1).

#???????????°?????° ?´?????¶???° ???????°???? ?´?°???????? ???? stdin ?? ?????????´?????? ???????????? ?? stdout.

#???????????? ???????´?????? ?´?°???????? (???? ???´?????? ?????´???????????´?????°?????????????????? ???° ????????????, ???°?????????°???????°?? ?´???????° ?????´???????????´?????°?????????????????? ??? 50 ????????????????):
#6789
#111

#???????????? ?????????´?????? ?´?°????????:
#6
#12

# ?????????????? ?????????????????? ?´?? ?????????° ????????????, ?????? ?????? ???????????´?????°?????????????????? ???? ???°???´???????????? ??????????
def prov(pos,s):
    ch = int(s[:pos])+1
    k1 = pos
    k2 = pos + len(str(ch))
    while k2 < len(s):
        if str(ch) == s[k1:k2]:
            ch = ch +1
            k1 = k2
            k2 = k1 + len(str(ch))
        else:
            return -1
    if str(ch)[:len(s)-k1]!=s[k1:]:
        return -1
    return 0

#?????????????? ?????????????????? ?´???? ?????????????? ???????????????° ?????????° ?????? ?????????? ?? ???????????´?????°??????????????????
def sf(ch):
    #print(ch)
    s = '1'
    for i in range(len(str(ch)) - 1):
        s = s + '0'
    l = len(str(ch))
    otv = (ch - int(s)) * l + 1
    l = l - 1
    while l > 0:
        otv = otv + (int(s[:l + 1]) - int(s[:l])) * l
        l = l - 1
    return otv

# ??-?????? ?????±?????????????? ???°???±?????°???? ???????????? ???° ???????????????? ???????????´?????°??????????????????
def last(s):
    if (len(s) == 1) & (s != '0'):
        return int(s)
    if (s == '0'):
        return 11
    for pos in range(1,len(s)): # pos - ?????????´?????????? ?????????´???? ?????????°
        for start in range (pos+1): # start - ???°???°???? ?????????????? ???? ???°???±?????????? ???????????´?????°???????????????????? ?????????°
            if start == 0: # ???????? ???????°???°????, ?????? ???????????´?????°?????????????????? ???°???????°???????? ?? ?????????°
                if prov(pos,s)!= -1:
                    return sf(int(s[start:start+pos]))
                if s[:1] == '0': # ???????? ?????? ???????????° ????????
                    if s == '0'*len(s):
                        return sf(int('1'+s))+1
            else: # ???????? ???????? ???????????? ?????????? ???? ?????°???°???° ???????????´?????°??????????????????
                if start + pos <len(s):
                    if (s[:start] == str(int(s[start:start+pos])-1)[len(str(int(s[start:start+pos])-1))-start:]):
                        if prov(pos, s[start:]) != -1:
                            return sf(int(s[start:start + pos])-1)+len(str(int(s[start:start + pos])-1))-start
                else:
                    if (pos + start > len(s) - 1) & (start > 0): # ?´???? ?????????°???? ???????´?° ???????????° ?????´?????¶???? ?????????? ?´???° ?????????° ?? ?????? ???±?° ???? ????????????
                        ch = str(int(s[:start]) + 1)
                        if len(ch) > len(s[:start]):
                            ch = ch[1:]
                        ch1 = s[start:]
                        i = len(ch)
                        if ch == ch1[len(ch1) - len(ch):]:
                            return sf(int(ch1)-1)+len(str(int(ch1)-1))-start
                        while (i > 0) & (ch[:i] != ch1[len(ch1) - i:]):
                            i = i - 1
                        ich = -1
                        if s[:len(ch[:i])] == ch[:len(ch[:i])]:
                            ich = int(s[:len(s)-len(ch[:i])])
                            s1 = s[len(ch[:i])+1:len(s)-len((ch[:i]))]
                            k = len(ch[:i])+1
                        else:
                            s1 = s[len(ch[:i]):len(s)-len((ch[:i]))]
                            k = len(ch[:i])
                        if i != 0:
                            x = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
                            for j in range(9):
                                if s1.find(x[j])!= -1:
                                    k = k + s1.find(x[j])
                                    break
                            if (ich!=-1)&(ich<int(s[k:len(s)-len((ch[:i]))]+s[:k])):
                                return sf(ich)
                            else:
                                return sf(int(s[k:len(s)-len((ch[:i]))]+s[:k]))+len(str(int(s[k:len(s)-len((ch[:i]))]+s[:k])))-k

    x = ['1', '2', '3', '4', '5', '6', '7', '8', '9']  #???????? ???? ???°?????? ???°???????° ???° ???????????´?????°??????????????????, ???????????? ???? ???????????????????? ???????????°?????????? ??????????
    for i in range(9):
        if s.find(x[i]) != -1:
            ch = int(s[s.find(x[i]):] + s[:s.find(x[i])])
            k = s.find(x[i])
            pos = k
            while s[k:].find(x[i]) != -1:
                if int(s[s[k:].find(x[i]):] + s[:s[k:].find(x[i])]) < ch:
                    ch = int(s[s[k:].find(x[i]):] + s[:s[k:].find(x[i])])
                    pos = k
                k = k + s[k:].find(x[i]) + 1
            return sf(int(s[s.find(x[i]):] + s[:s.find(x[i])]))+len(s[s.find(x[i]):] + s[:s.find(x[i])]) - pos
    return 0


m = [] #???°???????? ???????´?????? ?´?°????????
s = str(input())  #???????°???? ??????????????????
while s!='': # ???????????? ?´?°???????? ?´?? ???????????? ????????????
    if s.isdigit(): #???????? ???????????° ?????´?????¶???? ???????????? ?????????°, ???°???????????°???? ????
        m.append(s)
    else:
        print('String is not a sequence of numbers')
    s = str(input())

for i in range(len(m)): # ?????????°???? ?´???? ???°?¶?´???? ????????????
    print(last(m[i]))