Dragon Curve [Summer Festival Contest 3]

コンテスト: https://hoj.hamako-ths.ed.jp/onlinejudge/contest/106/problems/3
アーカイブ: https://hoj.hamako-ths.ed.jp/onlinejudge/problems/837

解法

https://hoj.hamako-ths.ed.jp/onlinejudge/state/25956

ICPCにも同じっぽいのが出てたけど、とにかくまずは実験してみる。
すると、

第1群 初項1, 公差2の数列の番目(1,3,5,7,9,...)だけで見ると、谷山谷山…になっている
第2群 初項2, 公差4の数列の番目(2,6,10,14,...)だけで見ると、谷山谷山…になっている
第3群 初項4, 公差8の数列の番目(4,12,20,28,...)だけで見ると、谷山谷山…になっている
...
第n群 初項2^(n-1), 公差2^nの数列の番目だけで見ると、谷山谷山…になっている

ということが分かる。
なので、群について全探索をして、Dが第何群に属しているかを探す。
あとは、その群で何番目かの偶奇を見れば山か谷かが分かる。

typedef long long ll;
ll N, D;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
 
    ll a = 1, d = 2;
    rep(i, 0, 60) {
        if ((D - a) % d == 0) {
            int n = (D - a) / d;
            if (n % 2 == 0) printf("TANI\n");
            else printf("YAMA\n");
            return;
        }
        a *= 2;
        d *= 2;
    }
}