【对称美学】
对称就是最大的美学,现有一道关于对称字符串的美学。
已知:
第 1 个字符串:R
第 2 个字符串:BR
第 3 个字符串:RBBR
第 4 个字符串:BRRBRBBR
第 5 个字符串:RBBRBRRBBRRBRBBR
相信你已经发现规律了,没错!
就是第i个字符串 = 第i-1号字符串的取反 + 第i-1号字符串。
取反即(R->B, B->R);
现在告诉你 n 和 k ,让你求得第n个字符串的第k个字符是多少。
(k的编号从0开始)
输入描述
第一行输入一个 T ,表示有 T 组用例:
接下来输入 T行,每行输入两个数字, 表示 n , k
1 <= T <= 100;
1 <= n <= 64;
0 <= k < 2^(n-1);
代码解题:暴力破解存储会爆内存
思路:
1.如果我们要找到的k位于第n个字符串的后半部分,假设为get(n, k),那么其等价于 get(n-1, k -2^(n-2),依次递归,直至退到n=1和2
2.那么如果第k个字符串位于第n个字符串的前半部分,可以发现,其实get(n,k),如果k <= 2^(n-2) ,则相当于 get(n-1, k) 的颜色取反。
t = int(input())
datas = [list(map(int,input().split()))for i in range(t)]
def getData(n,k):
if n == 1:
return 'red'
elif n == 2:
if k == 0:
return 'blue'
else:
return 'red'
middle = 2**(n-1)//2
if middle <= k:
return getData(n-1,k-middle)
else:
if getData(n-1,k) == 'red':
return 'blue'
else:
return 'red'
for n,k in datas:
print(getData(n,k))