ABC 027 C 倍々ゲーム

2015/08/09 (Sun) ABC AtCoder OEIS アドホック ☆

問題

問題文

方針

TLE する DFS を書いて実験して $0$ と $1$ が切り替わるところの数列を作り、 OEIS で検索した． その結果，漸化式は $a_n = 4a_{n-2} + 2, a_0=0, a_1=1$ だということが分かるので生成して埋め込む．

想定解はとても頭がいいです。さすが sugim プロとしか言えないです。

実装

// TLE します
bool rec(ll cur, ll n){
    if (cur > n) return true;
    return !(rec(2*cur,n) && rec(2*cur+1,n));
}
bool solve2(ll n){
    return rec(1,n);
}

ll a[] = {
    0LL,
    1LL,
    2LL,
    6LL,
    10LL,
    26LL,
    42LL,
    106LL,
    170LL,
    426LL,
    682LL,
    1706LL,
    2730LL,
    6826LL,
    10922LL,
    27306LL,
    43690LL,
    109226LL,
    174762LL,
    436906LL,
    699050LL,
    1747626LL,
    2796202LL,
    6990506LL,
    11184810LL,
    27962026LL,
    44739242LL,
    111848106LL,
    178956970LL,
    447392426LL,
    715827882LL,
    1789569706LL,
    2863311530LL,
    7158278826LL,
    11453246122LL,
    28633115306LL,
    45812984490LL,
    114532461226LL,
    183251937962LL,
    458129844906LL,
    733007751850LL,
    1832519379626LL,
    2932031007402LL,
    7330077518506LL,
    11728124029610LL,
    29320310074026LL,
    46912496118442LL,
    117281240296106LL,
    187649984473770LL,
    469124961184426LL,
    750599937895082LL,
    1876499844737706LL,
    3002399751580330LL,
    7505999378950826LL,
    12009599006321322LL,
    30023997515803306LL,
    48038396025285290LL,
    120095990063213226LL,
    192153584101141162LL,
    480383960252852906LL,
    768614336404564650LL,
    1921535841011411626LL,
    3074457345618258602LL,
    7686143364045646506LL
};

int len = sizeof(a)/sizeof(ll);

bool solve(ll n){
    rep(i,len) if(a[i] > n) return i&1;
    assert(false);
}

int main(){
    ll n;
    cin >> n;
    puts(solve(n) ? "Takahashi" : "Aoki");
}