きれい

問題概要

$N$ 枚のコインがあります。高橋君と青木君は、以下の操作を高橋君から始めて交互に繰り返します。

0 以上の整数 $k$ を選び、コインを $8^{k}$ 枚取り除く。

先に操作を行えなくなった者の負けです。両者が最適に行動するとき、どちらが勝つでしょうか？

制約

$1 \le N \le 10^{18}$

考えたこと

もしこれが ARC-D 問題に出題されたとして、冷静に「実験しよう」と思えるだろうか...

実験すると確かに見えて来る。実験するとしたら、例えば以下のように書ける (このようなゲームを実験するときの書き方についてはこの記事などに書いた)。

#include <iostream>
#include <cstring>
using namespace std;

int dp[110000];
int iswin(long long n) {
    if (n == 0) return 0;
    if (dp[n] != -1) return dp[n];
    
    long long eight = 1;
    while (eight <= n) {
        if (!iswin(n - eight)) return dp[n] = 1; // 相手に「負け」を渡せたら勝ち
        eight *= 8;
    }
    return dp[n] = 0;
}

int main() {
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= 100; ++i) {
        cout << i << ": " << iswin(i) << endl;
    }
}

これを出力すると、以下のようになる

じっと眺めると、周期 9 で、

0, 1, 0, 1, 0, 1, 0, 1, 1

を繰り返していることがわかる。証明は後に回すとして、この通りに実装すると通る。

#include <iostream>
using namespace std;

int ans[9] = {0, 1, 0, 1, 0, 1, 0, 1, 1};

int main() {
    long long n;
    cin >> n;
    if (ans[n%9]) cout << "Win" << endl;
    else cout << "Lose" << endl;
}