結果

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

ソースコード

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) {
    bool rev = false;  // counts how many “turn‐swaps” we did
    bool res = false;  // what the eventual base‐case says

    while (true) {
        // keep a >= b
        if (a < b) swap(a, b);

        // now a >= b > 0
        int64 q = a / b;
        int64 r = a % b;

        if (r == 0) {
            // you can divide exactly to 0 ⇒ win immediately
            res = true;
            break;
        }
        if (q >= 2) {
            // forced mod with q>=2 hands a winning position to opponent ⇒ you lose
            res = false;
            break;
        }
        // q == 1, r > 0: only move is (a,b)→(b,r) and it's opponent's turn
        a = b;
        b = r;
        rev = !rev;
    }

    // if we swapped an odd number of times, invert the base‐case result
    return rev ? !res : res;
}

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