问题描述
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^12
输入
输入第一行为查询次数，后面为每次查询的具体字符位置。
输出
输出每一次查询位置上的字符。
示例输入
2
3
10
示例输出
3
2
思路
每次迭代，A的长度翻倍并增加i，i为迭代次数。则A的具体值如下图所示：
（寻找可递归的部分）可以看出对于第i组，A的开头都是i个$，后面的部分与第1~第i-i组的拼接结果相同。那么如果寻找的位置find落在第i组，如果find小于head，则结果为$；否则令find=find-head+1，递归地再次求解。
python代码
def GetChar(q):
g_str = ['1', '2', '3', '4', '5', '$', '5', '4', '3', '2', '1']
while q > len(g_str):
m, itr = GetValues(q)
val = int(((m - itr) / 2) + itr);
if(q <= val):
q = 6
break
q -= val
if(q > 0):
return g_str[q-1]
return ""
def GetValues(q):
size = 5;
itr = 0;
while True:
if(q <= size):
return (size, itr)
itr += 1;
size = (size * 2) + itr
T = int(input())
for i in range(0, T):
q = int(input())
print(GetChar(q))
