描述
一组字符串s_i满足如下定义:
i=0时,s_0 = "words"
i>0时,s_i = "Listeningtoyour" + s_{i-1} + "likelisteningtothe" + s_{i-1}
其中加号代表字符串拼接。
你的任务是,输出s_n的第k个字符。
输入INPUT:
输入格式
第一行包括一个整数T,代表T组数据。
接下来每行两个整数n,k,代表查询s_n的第k个字符。
数据范围:
对于10%的数据,n = 0
对于20%的数据,n ≤ 1
对于40%的数据,n ≤ 6, k ≤ 1000, T ≤ 10
对于60%的数据,n ≤ 12, k ≤ 10^5, T ≤ 100
对于80%的数据,n ≤ 30, k ≤ 10^6, T ≤ 1000
对于100%的数据,0 ≤ n ≤ 100, 1 ≤ k ≤ 10^{18}, T ≤ 10^5
输入样例
5
0 3
2 73
2 43
1 23
2 120
输出OUTPUT:
输出格式
每行输出一个字符,代表答案。如果s_n的长度不足k,输出字符*。
s_1 = "Listeningtoyourwordslikelisteningtothewords"
s_2 = "ListeningtoyourListeningtoyourwordslikelisteningtothewordslikelisteningtotheList eningtoyourwordslikelisteningtothewords"
输出样例
r
o
t
k
*
下面是我的代码了,求debug:
#include <iostream>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
ll len[110];
char s1[100],s2[100];
char f(int x,ll n){
if(x==0){
return "word"[n-1];
}
if(n>15+len[x-1]&&n<=33+len[x-1]*2){
return s2[n-1-len[x-1]-15];
}
if(n>15&&n<=15+len[x-1]){
return f(x-1,n-15);
}
if(n>33+len[x-1]*2){
return f(x-1,n-33-len[x-1]);
}
if(n<=15){
return s1[n-1];
}
}
int main(){
ll t,n,k;
strcpy(s1,"Listeningtoyour");
strcpy(s2,"likelisteningtothe");
len[0]=4;
for(int i=1;i<=100;i++){
len[i]=33+len[i-1]*2;
}
cin>>t;
for(int i=0;i<t;i++){
cin>>n>>k;
if(len[n]<k)cout<<"*\n";
else cout<<f(n,k)<<"\n";
}
return 0;
}