結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 11:37:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,851 bytes
コンパイル時間 929 ms
コンパイル使用メモリ 80,864 KB
実行使用メモリ 225,224 KB
最終ジャッジ日時 2025-04-19 11:37:22
合計ジャッジ時間 7,407 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 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)?
// Returns true if the current player wins, false otherwise.
bool can_win(long long my, long long opp) {
    // Base cases
    if (my == 0) return false; // The previous player made my number 0, so they win, I lose.
    if (opp == 0) return true;  // I made the opponent's number 0 on my previous turn, so I win.

    // Check memoization
    if (memo.count({my, opp})) {
        return memo[{my, opp}];
    }

    // Winning moves: make my number 0 on this turn
    if (my == 1) return memo[{my, opp}] = true; // Subtract to 0
    if (my >= opp && my % opp == 0) return memo[{my, opp}] = true; // Remainder to 0

    // Recursive step: current player wins if they can move to a state where the opponent loses

    // Case 1: my < opp
    if (my < opp) {
        // Must subtract. Opponent faces state (opp, my - 1).
        // Current player wins if opponent loses from (opp, my - 1).
        return memo[{my, opp}] = !can_win(opp, my - 1);
    }

    // Case 2: my >= opp
    // Option 1: Use remainder operation (if my % opp != 0)
    bool can_win_by_remainder = false;
    if (my % opp != 0) {
        // Opponent faces state (opp, my % opp).
        // Current player wins if opponent loses from (opp, my % opp).
        if (!can_win(opp, my % opp)) {
            can_win_by_remainder = true;
        }
    }

    // If we can win by remainder, take it.
    if (can_win_by_remainder) {
        return memo[{my, opp}] = true;
    }

    // If cannot win by remainder (or remainder not applicable, i.e., my % opp == 0 which is an immediate win),
    // consider the subtract move.
    // Apply the hypothesis: if my / opp >= 2, subtracting is a losing move if remainder wasn't winning.
    // We only explore the subtract path if my / opp == 1.
    if (my / opp >= 2) {
        // Remainder wasn't winning (or not applicable and not an immediate win),
        // and subtract is losing (by hypothesis when my/opp >= 2). Current player loses.
        return memo[{my, opp}] = false;
    } else { // my / opp == 1
        // Check the subtract move.
        // Opponent faces state (opp, my - 1).
        // Current player wins if opponent loses from (opp, my - 1).
        bool can_win_by_subtract = !can_win(opp, my - 1);
        return memo[{my, opp}] = can_win_by_subtract;
    }
}

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

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

    // Alice starts the game with numbers A and B.
    // Alice wins if can_win(A, B) is true.
    if (can_win(A, B)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0