結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 11:30:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,499 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 80,868 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-04-19 11:30:44
合計ジャッジ時間 4,987 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility> // for pair

using namespace std;

map<pair<long long, long long>, bool> memo;

// Can the current player win starting with numbers (my, opp)?
// 'my' is the current player's number, 'opp' is the opponent's number.
bool can_win(long long my, long long opp) {
    // Base case: If my number is 0, the previous player (opponent) made it 0 and won. So, I lose.
    if (my == 0) {
        return false;
    }
    // Base case: If opponent's number is 0, I made it 0 on my previous turn and won. So, I win.
    if (opp == 0) {
        return true;
    }

    // Use memoization to avoid recomputing states
    if (memo.count({my, opp})) {
        return memo[{my, opp}];
    }

    // Check for immediate win by remainder operation
    // If my >= opp and my % opp == 0, I can replace my with 0 and win this turn.
    if (my >= opp && my % opp == 0) {
        return memo[{my, opp}] = true; // Current player wins immediately
    }

    // Evaluate possible moves for the current player

    // Option 1: Subtract 1 from my number
    // The new state for the opponent will be (opp, my - 1).
    // I win by this move if the opponent loses from that state.
    bool can_win_with_subtract = !can_win(opp, my - 1);

    // If winning by subtracting 1 is possible, I win from this state.
    if (can_win_with_subtract) {
        return memo[{my, opp}] = true;
    }

    // Option 2: Replace my number with my % opp (if my >= opp and my % opp != 0)
    // The case my % opp == 0 is handled as an immediate win above.
    if (my >= opp) {
        // The new state for the opponent will be (opp, my % opp).
        // I win by this move if the opponent loses from that state.
        bool can_win_with_remainder = !can_win(opp, my % opp);

        // If winning by using the remainder operation is possible, I win from this state.
        if (can_win_with_remainder) {
            return memo[{my, opp}] = true;
        }
    }

    // If no winning move is found after checking all possibilities, the current player loses.
    return memo[{my, opp}] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long A, B;
    cin >> A >> B;

    // Alice goes first with numbers A and B.
    // Call can_win with Alice's number as 'my' and Bob's number as 'opp'.
    if (can_win(A, B)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0