結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 12:08:48
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,201 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,434 ms
コンパイル使用メモリ 81,092 KB
実行使用メモリ 133,832 KB
最終ジャッジ日時 2025-04-19 12:08:56
合計ジャッジ時間 7,964 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

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


// can_win(my, opp): Can the player whose turn it is, starting with numbers (my, opp), force a win?
bool can_win(long long my, long long opp) {
    // Base case 1: If my number is 0, I cannot make a move to win. This state implies I lost on a previous turn.
    if (my == 0) return false;

    // Base case 2 & Immediate Win: Check if I can make my number 0 this turn.
    if (my == 1) return true; // Operation 1: Subtract 1 to make it 0.
    if (my >= opp && my % opp == 0) return true; // Operation 2: Use Remainder to make it 0 (if applicable).

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

    bool res; // Result for the current state (my, opp)

    if (my < opp) {
 
        res = !can_win(opp, my - 1);
    } else { // my >= opp and my % opp != 0 (Immediate win handled above)
        long long q = my / opp; // Quotient
        long long r = my % opp; // Remainder (r > 0 because my % opp != 0)


        bool can_win_by_remainder = !can_win(opp, r);


        if (q == 1) { // Case: opp <= my < 2 * opp and my % opp != 0
            // Both Remainder (to (opp, r)) and Subtract (to (opp, my-1)) are important moves.
            // I win if either move leads to a state where the opponent loses.
            bool can_win_by_subtract = !can_win(opp, my - 1);
            res = can_win_by_remainder || can_win_by_subtract;
        } else { // Case: q >= 2 (my >= 2 * opp)
            res = can_win_by_remainder || (q % 2 == 1);
        }
    }

    // Store the computed result in the memoization table for the current state (my, opp)
    return memo[{my, opp}] = res;
}

int main() {
    // Optimize input/output operations
    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