Nephren gives a riddle [Codeforces Round #449 A]

http://codeforces.com/contest/896/problem/A

f[0] = What are you doing at the end of the world? Are you busy? Will you save us?
f[i] = What are you doing while sending "f[i - 1]"? Are you busy? Will you send "f[i - 1]"?
の漸化式で表現される文字列がある。

Q個の以下のクエリの結果を繋げた文字列を答えよ。
f[n]のk番目の文字を答える（kが文字長を超えている場合は'.'と答える）

解法

http://codeforces.com/contest/896/submission/32865296

よくある再帰構築をする。
「cnt[i] := S[i]の長さ」をまず作るが、指数的に大きくなるので一定ラインを超えたら丸めるようにする。
今回は参照されるkが10^18以下なので、このラインを使えばいい。
　
使う文字列を以下のように定義しておく。
string f0 = "What are you doing at the end of the world? Are you busy? Will you save us?";
string a = "What are you doing while sending \"";
string b = "\"? Are you busy? Will you send \"";
string c = "\"?";
　
f(n,k) := S[n]のk番目の文字
これを再帰的に解決していく。
「f[n] = a + f[n-1] + b + f[n-1] + c」と連結されているので、kの値とcnt[n-1]を見ながら、この5つの文字列のどこに属するかを求める。
a,b,cのどれかに属するなら、その文字を返せばいい。
もし、f[n-1]に属するなら、f(n-1,k')で再帰的に処理を投げる。
kが文字列cより後を指すならば'.'を返す。

string f0 = "What are you doing at the end of the world? Are you busy? Will you save us?";
string a = "What are you doing while sending \"";
string b = "\"? Are you busy? Will you send \"";
string c = "\"?";
//---------------------------------------------------------------------------------------------------
typedef long long ll;
ll cnt[101010];
#define INF 1LL<<60
void pre() {
    cnt[0] = f0.size();
    rep(i, 1, 101010) {
        cnt[i] = (ll)a.size() + (ll)b.size() + (ll)c.size() + 2LL * cnt[i - 1];
        if (cnt[i] < cnt[i - 1]) cnt[i] = INF;
    }
}
char f(int n, ll k) {
    if (n == 0) {
        if (k < f0.size()) return f0[k];
        else return '.';
    }

    if (k < a.size()) return a[k];
    k -= a.size();

    if (k < cnt[n - 1]) return f(n - 1, k);
    k -= cnt[n - 1];

    if (k < b.size()) return b[k];
    k -= b.size();

    if (k < cnt[n - 1]) return f(n - 1, k);
    k -= cnt[n - 1];

    if (k < c.size()) return c[k];

    return '.';
}
//---------------------------------------------------------------------------------------------------
void _main() {
    pre();

    int Q; cin >> Q;
    string ans = "";
    rep(i, 0, Q) {
        int n; ll k; cin >> n >> k; k--;
        ans += f(n, k);
    }
    cout << ans << endl;
}