結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー Mistletoe
提出日時 2025-04-19 09:32:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,147 bytes
コンパイル時間 2,167 ms
コンパイル使用メモリ 191,952 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 09:32:41
合計ジャッジ時間 3,881 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 52 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

// returns true if the player to move, holding 'a' while the opponent holds 'b', has a winning strategy
bool win(int64 a, int64 b) {
    // base cases
    if (a == 0) return false;   // no moves, so current player loses
    if (b == 0) return true;    // opponent has zero—this state can't actually occur in play, but treat as win

    // if a == 1, one subtract wins immediately
    if (a == 1) return true;
    // if b == 1, only subtracts are possible on your side, so you'll take 'a' moves;
    // you win iff that number of turns (on your own moves) arrives before opponent
    // but in fact one can show that this reduces to parity of a:
    //   if a is odd, Alice (who moves first among the pair) wins; otherwise Bob
    // however, since here we're looking at the position for whichever player to move,
    // and they need exactly 'a' of their own moves to finish, they win if and only if
    //   a % 2 == 1
    if (b == 1) return (a % 2 == 1);

    // now both a, b >= 2

    if (a < b) {
        // when b >= 2a, opponent on their move could divide by you twice (b/a >= 2)
        // and thus finish quickly; so if b/a >= 2, current player loses immediately
        int64 q = b / a;
        if (q >= 2)
            return false;
        // otherwise b/a == 1, so opponent can only reduce b -> b - a in one step.
        // We swap roles and hands: the next position is (b - a, a), and it's the opponent's move.
        // So current wins exactly when that position is losing for them:
        return !win(b - a, a);
    }
    else {
        // a >= b
        // if we can divide by opponent at least twice, we can force a win in one go
        int64 q = a / b;
        if (q >= 2)
            return true;
        // otherwise a/b == 1, so our only “big” move is a -> a - b.
        // After that, roles swap and it's opponent's turn on (b, a - b).
        return !win(b, a - b);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 A, B;
    cin >> A >> B;
    cout << (win(A, B) ? "Alice\n" : "Bob\n");
    return 0;
}
0