Millie oj finds the number N, number II

Articles Catalogue

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 = [0]*w
    seqstart[0] = 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 = [0]*w
    seqstart[0] = 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