Codeforces Round #449 (Div. 2) C. Nephren gives a riddle

痛定思痛。 2021-09-15 23:24 132阅读 0赞

C. Nephren gives a riddle  
time limit per test2 seconds  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output  
What are you doing at the end of the world? Are you busy? Will you save us?

Nephren is playing a game with little leprechauns.

She gives them an infinite array of strings, f0… ∞.

f0 is “What are you doing at the end of the world? Are you busy? Will you save us?”.

She wants to let more people know about it, so she defines fi =  “What are you doing while sending “fi - 1”? Are you busy? Will you send “fi - 1”?” for all i ≥ 1.

For example, f1 is

“What are you doing while sending “What are you doing at the end of the world? Are you busy? Will you save us?”? Are you busy? Will you send “What are you doing at the end of the world? Are you busy? Will you save us?”?”. Note that the quotes in the very beginning and in the very end are for clarity and are not a part of f1.

It can be seen that the characters in fi are letters, question marks, (possibly) quotation marks and spaces.

Nephren will ask the little leprechauns q times. Each time she will let them find the k-th character of fn. The characters are indexed starting from 1. If fn consists of less than k characters, output ‘.’ (without quotes).

Can you answer her queries?

Input  
The first line contains one integer q (1 ≤ q ≤ 10) — the number of Nephren’s questions.

Each of the next q lines describes Nephren’s question and contains two integers n and k (0 ≤ n ≤ 105, 1 ≤ k ≤ 1018).

Output  
One line containing q characters. The i-th character in it should be the answer for the i-th query.

Examples  
inputCopy  
3  
1 1  
1 2  
1 111111111111  
outputCopy  
Wh.  
inputCopy  
5  
0 69  
1 194  
1 139  
0 47  
1 66  
outputCopy  
abdef  
inputCopy  
10  
4 1825  
3 75  
3 530  
4 1829  
4 1651  
3 187  
4 584  
4 255  
4 774  
2 474  
outputCopy  
Areyoubusy  
Note  
For the first two examples, refer to f0 and f1 given in the legend.

[题目][Link 1]

题意：给了你一个字符串f0  f 0 ,然后给了一个生成接下来字符串的公式.要你给出第n个字符串的k个位置是什么，假如超过的输出”.”  
**解题**  
我们先存下第n个字符串的位数，很容易想到很快就会超过1e18  
fn  f n  = pre  p r e  \+ f(n−1)  f ( n − 1 )  \+ mid  m i d  \+ f(n−1)  f ( n − 1 )  \+ last  l a s t   
然后就是一个递归的求解的过程，有很多情况，注意不出现错误就行

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    //head
    
    ll f[110010],p,m,l,n,k;
    string str,pre,mid,last;
    
    char solve(ll n,ll k)
    {
        if(k>f[n])
            return '.';
        if(n == 0)
            return str[k - 1];
        if(k <= p)
        {
            return pre[k - 1];
        }
        if(k <= p + f[n-1])
            return solve(n-1,k - p);
        if(k <= p + f[n-1] + m)
            return mid[k - 1 - p - f[n-1]];
        if(k <= p + f[n-1] + m + f[n-1])
            return solve(n-1,k - p - m - f[n-1]);
            return last[k - 1- (p + f[n-1] + m + f[n-1])];
    }
    int main()
    {
        str = "What are you doing at the end of the world? Are you busy? Will you save us?";
        pre = "What are you doing while sending \"";
        mid = "\"? Are you busy? Will you send \"";
        last = "\"?";
        p = pre.size();
        m = mid.size();
        l = last.size();
        f[0] = str.size();
        rep(i,1,100)
        {
            f[i] = 2*f[i-1] + p + m + l;
            if(f[i]>1e18)
                f[i] = 1e18+10;
        }
        rep(i,100,100001)
        {
            f[i] = 1e18+10;
        }
        int t;
        cin>>t;
        string ans;
        while(t--)
        {
            cin>>n>>k;
            ans += solve(n,k);
        }
        cout<<ans<<endl;
    }

[Link 1]: http://codeforces.com/contest/897/problem/C%20