結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 00:18:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,228 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 121,104 KB
最終ジャッジ日時 2025-04-19 00:18:56
合計ジャッジ時間 4,227 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# 尝试增加递归深度限制
try:
    # 设置一个足够大的值，例如 200000 或更大
    # 具体需要多大取决于 A, B 的值和游戏路径
    sys.setrecursionlimit(200000) 
except Exception as e:
    # 在某些环境可能无法设置，打印警告
    print(f"Warning: Could not set recursion depth limit. {e}")

memo = {} # 记忆化字典

def canWin(A, B):
    # Base case 1: 对手 B 的数字 <= 0, 当前玩家 A 获胜
    if B <= 0: 
        return True
    # Base case 2: 当前玩家 A 的数字 <= 0, 当前玩家 A 失败
    if A <= 0: 
        return False

    # 检查记忆化
    state = (A, B)
    if state in memo: 
        return memo[state]

    # Base case 3: 检查 A 是否能通过一步操作获胜
    # 3a: 如果 A = 1, 可以 A -> 0 获胜
    if A == 1:
        memo[state] = True
        return True
    # 3b: 如果 B <= A 且 A 是 B 的倍数, 可以 A -> A mod B = 0 获胜
    # (B > 0 隐含在此处，因为 B <= 0 已被处理)
    if B <= A and A % B == 0:
        memo[state] = True
        return True

    # 应用核心假设: 如果 A >= 2*B，当前玩家 A 必胜
    # (B > 0 隐含在此处)
    if A >= 2 * B:
        memo[state] = True
        return True

    # 递归情况
    # 情况 1: A < B
    if A < B:
        # 唯一操作 A -> A-1. 检查对手是否从 (B, A-1) 失败
        result = not canWin(B, A - 1)
        memo[state] = result
        return result
    # 情况 2: B <= A < 2B (且 A % B != 0)
    else:
        # 尝试操作 A -> A mod B = A - B. 检查对手是否从 (B, A-B) 失败
        win_by_mod = not canWin(B, A - B)
        if win_by_mod:
            memo[state] = True
            return True

        # 尝试操作 A -> A - 1. 检查对手是否从 (B, A-1) 失败
        win_by_dec = not canWin(B, A - 1)
        if win_by_dec:
            memo[state] = True
            return True

        # 若两种主要操作都不能确保胜利，则当前状态为必败
        memo[state] = False
        return False

# 读取输入
A, B = map(int, sys.stdin.readline().split())

# Alice 先手，判断 Alice 是否能从 (A, B) 状态获胜
if canWin(A, B):
    print("Alice")
else:
    print("Bob")
0