Description
Consider a string A = "12345". An infinite string s is built by performing infinite steps on A recursively. In i-th step, A is concatenated with '$' i times followed by reverse of A. A=A|$...$|reverse(A), where | denotes concatenation.
Constraints:1<=Q<=10^5, 1<=POS<=10^1
Input
输入第一行为查询次数，后面为每次查询的具体字符位置
Output
输出每一次查询位置上的字符。
Sample Input 1
2
3
10
Sample Output 1
3
2
Solution
INITIAL_STR = "12345"
def find_char(length, i, pos):
if i == 1:
str_1 = INITIAL_STR+'$'+INITIAL_STR[::-1]
return (str_1[pos-1])
else:
mid_begin = (length-i)//2 # 找到中间$开始的位置
mid_end = mid_begin + i-1 # 找到中间$结束的位置
if pos < mid_begin:
return find_char(mid_begin, i-1, pos) # 找左半部分
elif pos > mid_end:
return find_char(mid_begin, i-1, pos-mid_end-1) # 找右半部分
else:
return '$'
if __name__ == '__main__':
T = int(input())
while T:
T -= 1
pos = int(input())
length = len(INITIAL_STR)
i = 0
# 获得是第几次迭代
while pos > length:
i += 1
length = 2 * length + i
if i == 0:
print(INITIAL_STR[pos-1])
else:
print(find_char(length, i, pos))
