# subject

If a set of strings conforms to the following rules:
S1=1S2=12S3=123S4=1234...S9=123456789S10=12345678910S11=1234567891011⋯S18=123456789101112131415161718⋯ S _1 =1 \newline S _2=12 \newline S _3=123 \newline S _4 =1234 \newline \dots \newline S _9 =123456789 \newline S_{10} =12345678910 \newline S _{11} =1234567891011 \newline ⋯ \newline S _18 =123456789101112131415161718 \newline ⋯ S1​=1S2​=12S3​=123S4​=1234...S9​=123456789S10​=12345678910S11​=1234567891011⋯S1​8=123456789101112131415161718⋯

(For SnS_nSn, the numbers from 1 to nn are spliced together)

Now let's put all the strings together to form an infinite long string S = 1121234 456789101113 S = 1121234 cdots cdots S = 1121234 cdots S = 1124. Can you find out what the number of nn digits of the string is?

## input

An integer (1 < integer < 101510 ^ {15} 1015) indicates the number of digits required.

## output

An integer that represents the number on that bit.

## sample input

1
6
7
1234567
2345
234


## sample output

1
3
1
5
5
1


# Analysis

1. First, analyze how many numbers each row has.

The analysis table is as follows:

subsection Number of digits (i denotes line number)
S1−S9S_1 -S_9S1​−S9​ i
S10−S99S_{10} -S_{99}S10​−S99​ 9+ (i -9)*2
S100−S999S_{100} -S_{999}S100​−S999​ 9+ (99-9)*2+(i-99)*3

Based on this, the formula can be deduced:
Len(S(i))=∑w=1w=len(i)−1w{(10w−1)−(10w−1−1)}+∑w=len(i)−1w=len(i)−1{i−(10w−1)}w Len(S(i)) = \sum_{w=1}^{w=len(i)-1} w\{(10^w-1) -(10^{w-1}-1)\} + \sum_{w=len(i)-1}^{w=len(i)-1} \{ i-(10^w -1) \} w Len(S(i))=w=1∑w=len(i)−1​w{(10w−1)−(10w−1−1)}+w=len(i)−1∑w=len(i)−1​{i−(10w−1)}w

Writable function:

def lineLen(lineIndex):
# w denotes number of digits
w = len(str(lineIndex))

result = 0
for i in range(w):
t1 = '9'* (i+1)
t1 = int(t1)

if i == 0:
t2 = 0
else:
t2 = '9'*i
t2 = int(t2)

if i == w-1:
result += (lineIndex-t2) * (i+1)
else:
result += (t1-t2) * (i+1)

return result


Now we can use the function lineLen(lineIndex) to find the length of any line.

1. How many numbers are there in the first n rows?

The analysis shows that the sequence can be divided into several equal difference sequences.

The summation formula of the sequence of equal difference is as follows:

Ln=a1n+n(n−1)2d L_n = a_1 n + \frac{n(n-1)}{2} d Ln​=a1​n+2n(n−1)​d

The analysis table is as follows:

subsection The total number of the first i rows
L1−L9L_1 -L_9L1​−L9​ a1=1,n=i,d=1,L1(i)=a1n+n(n−1)2da_1 = 1, n = i, d = 1, \newline L_1(i)= a_1 n + \frac{n(n-1)}{2} da1​=1,n=i,d=1,L1​(i)=a1​n+2n(n−1)​d
L10−L99L_{10} -L_{99}L10​−L99​ a1=lineLen(10),n=i−9,d=2,L2(i)=L1(9)+a1n+n(n−1)2da_1 = lineLen(10), n = i-9, d = 2, \newline L_2(i)= L_1(9)+a_1 n + \frac{n(n-1)}{2} da1​=lineLen(10),n=i−9,d=2,L2​(i)=L1​(9)+a1​n+2n(n−1)​d
L100−L999L_{100} -L_{999}L100​−L999​ a1=lineLen(100),n=i−99,d=3,L3(i)=L1(9)+L2(99)+a1n+n(n−1)2da_1 = lineLen(100), n = i-99, d = 3, \newline L_3(i)= L_1(9)+L_2(99)+a_1 n + \frac{n(n-1)}{2} da1​=lineLen(100),n=i−99,d=3,L3​(i)=L1​(9)+L2​(99)+a1​n+2n(n−1)​d

The code is as follows:

# How many line s are there before calculating
def totalNum(line):
w = len(str(line))
seqstart = *w
seqstart = 1
for i in range(1,w):
seqstart[i] = lineLen(10**i)

resultsum = 0

for i in range(w):
if  i==w-1:
n = line- (10**i -1)
else :
n = 9*(10**i)
a1 = seqstart[i]
d = i+1
resultsum += n*a1 + (n*(n-1)/2) *d
return int(resultsum)

1. Find, need to find:
• The nth digit is in the row
• Find the row and find the number of changes.

Because the S(i) and L(i) sequences are incremental, the binary search method can be used.

The code is as follows:

# Use binary search to locate
def binaryFind(n,index,funcin):
start = 1
end = n+1
while start <= end:
mid = (start+end)//2
if funcin(mid) >= index and funcin(mid-1) < index :
return mid
elif funcin(mid) < index:
start = mid+1
else :
end = mid-1

return "not find "



## All code

import sys

def lineLen(lineIndex):
# Formula: L (n) = 9 * 1 + (99 - 9) * 2 +... + (n - 9... 9) * I

# w denotes number of digits
w = len(str(lineIndex))

result = 0
for i in range(w):
t1 = '9'* (i+1)
t1 = int(t1)

if i == 0:
t2 = 0
else:
t2 = '9'*i
t2 = int(t2)

if i == w-1:
result += (lineIndex-t2) * (i+1)
else:
result += (t1-t2) * (i+1)

return result

# Use binary search to locate
def binaryFind(n,index,funcin):
start = 1
end = n+1
while start <= end:
mid = (start+end)//2
if funcin(mid) >= index and funcin(mid-1) < index :
return mid
elif funcin(mid) < index:
start = mid+1
else :
end = mid-1

return "not find "

# How many line s are there before calculating
def totalNum(line):
w = len(str(line))
seqstart = *w
seqstart = 1
for i in range(1,w):
seqstart[i] = lineLen(10**i)

resultsum = 0

for i in range(w):
if  i==w-1:
n = line- (10**i -1)
else :
n = 9*(10**i)
a1 = seqstart[i]
d = i+1
resultsum += n*a1 + (n*(n-1)/2) *d
return int(resultsum)

def calculate(n):

line = binaryFind(n,n,totalNum)

index = n - totalNum(line-1)
# The number to look for at this point is the index number of s(line)
if index < 10 :
return index
indexNum = binaryFind(line,index,lineLen)
index = index - lineLen(indexNum-1)
indexNum = str(indexNum)
return indexNum[index-1]

if __name__ == "__main__":
for line in sys.stdin:
line = line.strip()
if line == "":
continue
num = int(line)
result = calculate(num)
print(result)


Posted on Fri, 06 Sep 2019 23:16:30 -0700 by inquisitive