結果

問題 No.3112 Decrement or Mod Game
ユーザー Mistletoe
提出日時 2025-04-19 09:37:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,641 bytes
コンパイル時間 2,250 ms
コンパイル使用メモリ 191,388 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 09:37:58
合計ジャッジ時間 3,901 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;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 A, B;
    cin >> A >> B;

    // We want to compute win(A,B) for the symmetric "mod‐only" Euclid game:
    //   win(a,b) = true  if current player to move wins,
    //              false otherwise.
    //
    // Recurrence (assume a>=b>0, swap if necessary):
    //   let q = a/b, r = a%b.
    //   if r==0       → current makes it zero and WINS
    //   else if q>=2  → forced mod (only move) still drops into a losing position ⇒ current LOSES
    //   else (q==1)   → only move is (b,r), and turn passes ⇒ win(a,b) = !win(b,r)
    //
    // We can unroll that with an iterative loop + a single boolean flip.

    int64 a = A, b = B;
    bool rev = false;   // how many ! flips we’ve done along the way
    bool ret = false;   // what the base‐case returns

    while (true) {
        if (a < b) swap(a, b);
        // now a >= b
        int64 q = a / b;
        int64 r = a % b;

        if (r == 0) {
            // current can reduce a to 0 immediately
            ret = true;
            break;
        }
        if (q >= 2) {
            // forced mod lands us in a winning position for the *next* player,
            // so current loses
            ret = false;
            break;
        }
        // q == 1 and r > 0: only move is (a,b) -> (b,r), turn flips
        a = b;
        b = r;
        rev = !rev;
    }

    // if we flipped an odd number of times, we invert ret
    bool win0 = rev ? !ret : ret;

    cout << (win0 ? "Alice\n" : "Bob\n");
    return 0;
}
0