結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 00:46:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 824 bytes
コンパイル時間 853 ms
コンパイル使用メモリ 75,540 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 00:46:21
合計ジャッジ時間 8,921 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 RE * 1
other RE * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

bool canWin(long long a, long long b, vector<vector<bool>>& dp) {
    if (a == 0) return false;
    if (b == 0) return true;
    if (dp[a][b] != -1) return dp[a][b];

    // 操作 1：将 a 减 1
    if (!canWin(a - 1, b, dp)) {
        dp[a][b] = true;
        return true;
    }

    // 操作 2：将 a 替换为 a % b
    if (a > b && !canWin(a % b, b, dp)) {
        dp[a][b] = true;
        return true;
    }

    dp[a][b] = false;
    return false;
}

int main() {
    long long a, b;
    cin >> a >> b;

    // 创建 DP 表，初始化为 -1
    vector<vector<bool>> dp(a + 1, vector<bool>(b + 1, -1));

    // Alice 先手
    if (canWin(a, b, dp)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0