ABC27C:倍々ゲーム-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

## 問題
$x=1$からスタートして、各プレイヤーが交互に$2x$か$2x+1$に変換する

$N$を超えたら負け。

解説ACでした

## 木を書いて実験する

こういう時に手が動かないのはだめだなあと反省

再帰的な感じで書くのかなと思ったんだけど、次負けないような手を打つぐらいしか戦略がわからず、どうシミュレートしていいかわからず。

今回の木はとても単純なので、Nが決まるとゲームが終了するノードとそれが誰の番なのかの候補がいくつか決まり、さらにそれらも単純なので最適戦略がすぐきまります。

例えば、
$N=10$だった場合、

ゲームの終了状態は、
```
(6,t) : x=6の状態でtakahashiの手番
(7,t)
(8,a)
(9,a)
(10,a)
```

となっています。(node,その時の手番)

(tはtakahashi,aはaoki)
この場合だとtakahashiは8,9,10のいずれかに数字を持っていければ勝ちなので常に数字を大きくする(つまり$2x+1$にする)のが最適戦略になります。

aokiさんはその逆で、6,7にすれば勝ちなので$2x$にし続けます。

一般には$N$の木の深さの偶奇によってこの戦略は変わります。

$N=5$の場合、終了状態は、

```
(3,a)
(4,t)
(5,t)
```

となり、今度は逆にtakahashiは数字を小さくし、aokiは大きくするのが最適になります。

## 実装

```python
N = int(input())

depth = 0

while 2**depth <= N:
    depth += 1

if depth % 2 == 0:
    def takahashi(x): return 2 * x

def aoki(x): return 2 * x + 1
else:
    def takahashi(x): return 2 * x + 1

def aoki(x): return 2 * x

x = 1
t_turn = True
while x <= N:
    if t_turn:
        x = takahashi(x)
    else:
        x = aoki(x)
    t_turn = not t_turn

print("Takahashi" if t_turn else "Aoki")

```

ABC27C:倍々ゲーム