Solutions CS101

Appearance

T01019: Number Sequence ​

binary search, http://cs101.openjudge.cn/practice/01019/

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910

输入

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

输出

There should be one output line per test case containing the digit located in the position i.

样例输入

2
8
3

样例输出

2
2

来源

Tehran 2002, First Iran Nationwide Internet Programming Contest

n * (n + 1) // 2 >= 2147483647。通过求解这个不等式，可以得到 n 的值约为 65535。第15行，print(ss) ，得到2406418995。

python
# 23n2300017711(杜昌钰)
# 生成递增的字符串序列
sequence = ""
s = 0
ss = 0
sums = []


for j in range(1, 33000):
    sequence += str(j)  # 将当前数字转换为字符串并追加到序列中
    s += len(str(j))
    ss += s  # 累加当前数字的长度
    sums.append(ss)  # 将累加和添加到列表中

#print(ss)

# 处理测试用例
test_cases = int(input())

for _ in range(test_cases):
    x = int(input())

    if x == 1:
        print(1)
    else:
        # 在累加和列表中查找第一个大于等于 x 的元素
        for i in range(len(sums)):
            if x <= sums[i]:
                # 计算偏移量并从序列中输出数字
                offset = x - sums[i-1] - 1
                print(sequence[offset])
                break

用bisect

python
import bisect
# 23n2300017711(杜昌钰)
# 生成递增的字符串序列
sequence = ""
s = 0
ss = 0
sums = []


for j in range(1, 33000):
    sequence += str(j)  # 将当前数字转换为字符串并追加到序列中
    s += len(str(j))
    ss += s  # 累加当前数字的长度
    sums.append(ss)  # 将累加和添加到列表中

# 处理测试用例
test_cases = int(input())

for _ in range(test_cases):
    x = int(input())

    if x == 1:
        print(1)
    else:
        # 在累加和列表中查找第一个大于等于 x 的元素
        # for i in range(len(sums)):
        #     if x <= sums[i]:
        #         # 计算偏移量并从序列中输出数字
        #         offset = x - sums[i-1] - 1
        #         print(sequence[offset])
        #         break
        i = bisect.bisect_left(sums, x)
        offset = x - sums[i - 1] - 1
        print(sequence[offset])

【陈子良 25物理学院】我做过的OJ题里二分查找题严重稀缺，没想到在这里看到了二分查找。题目就是找到数列112123123412345123456···中任意一位的数。直接打表会爆，注意到数列具有循环结构，我们只需要一个生成元s[i]=12345···就能找到目标数，再用另一个列表记录到s[i]为止的数列长度，这个列表就是单调递增的，可以用二分查找。

python
res=[1]
s=''
for i in range(1,40000):
    s+=str(i)
    res.append(res[-1]+len(str1))
t=int(input())
for _ in range(t):
    a=int(input())
    l=0
    r=len(res)
    while r-l>1:
        mid=(l+r)//2
        if res[mid]<=a:
            l=mid
        else:
            r=mid
    print(str1[a-res[l]])