結果

問題 No.3112 Decrement or Mod Game
ユーザー Rira
提出日時 2025-04-20 14:49:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 725 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 87,032 KB
実行使用メモリ 814,668 KB
最終ジャッジ日時 2025-04-20 14:49:46
合計ジャッジ時間 5,269 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

unordered_map<long long, unordered_map<long long, string>> dp;

string winner(long long a, long long b) {
    if (a == 0) return "Bob";
    if (b == 0) return "Alice";

    if (dp[a][b] != "") return dp[a][b];

    // 操作1: a を 1 減らす
    if (winner(a - 1, b) == "Bob") {
        dp[a][b] = "Alice";
        return "Alice";
    }

    // 操作2: a を b で割ったあまりに置き換える
    if (a >= b && winner(a % b, b) == "Bob") {
        dp[a][b] = "Alice";
        return "Alice";
    }

    dp[a][b] = "Bob";
    return "Bob";
}

int main() {
    long long A, B;
    cin >> A >> B;

    cout << winner(A, B) << endl;

    return 0;
}
0