結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-18 23:46:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,155 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 84,112 KB
実行使用メモリ 550,816 KB
最終ジャッジ日時 2025-04-18 23:46:21
合計ジャッジ時間 5,202 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility> // for std::pair
#include <algorithm> // for std::swap

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

bool solve(long long a, long long b) {

    if (memo.count({a, b})) {
        return memo[{a, b}];
    }

    bool res;

    if (a < b) {
        if (a - 1 == 0) {
            res = true;
        } else {
            res = !solve(b, a - 1);
        }
    } else { // a >= b
        if (a % b == 0) {
            res = true;
        } else {
            if (a / b > 1) {
                res = true;
            } else {
                bool can_win_by_mod_path = !solve(b, a % b);
                bool can_win_by_subtract_path = !solve(b, a - 1);
                res = can_win_by_mod_path || can_win_by_subtract_path;
            }
        }
    }

    return memo[{a, b}] = res;
}

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

    long long A, B;
    std::cin >> A >> B;
    
    if (solve(A, B)) {
        std::cout << "Alice" << std::endl;
    } else {
        std::cout << "Bob" << std::endl;
    }

    return 0;
}
0