結果

問題 No.102 トランプを奪え
ユーザー lam6er
提出日時 2025-03-31 17:42:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,734 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 309,316 KB
最終ジャッジ日時 2025-03-31 17:43:52
合計ジャッジ時間 10,984 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
from functools import lru_cache

def main():
    n = list(map(int, sys.stdin.readline().split()))

    @lru_cache(maxsize=None)
    def dfs(a, b, c, d, taro, jiro, turn):
        if a + b + c + d == 0:
            return taro - jiro

        best = -float('inf') if turn == 0 else float('inf')
        piles = [a, b, c, d]

        for i in range(4):
            if piles[i] == 0:
                continue
            for take in range(1, min(3, piles[i]) + 1):
                new_piles = list(piles)
                new_piles[i] -= take
                na, nb, nc, nd = new_piles
                new_taro = taro
                new_jiro = jiro

                if turn == 0:
                    new_taro += take
                else:
                    new_jiro += take

                if new_piles[i] == 0:
                    if turn == 0:  # Taro took the last
                        stolen = (new_jiro + 1) // 2
                        new_taro += stolen
                        new_jiro -= stolen
                    else:  # Jiro took the last
                        stolen = (new_taro + 1) // 2
                        new_jiro += stolen
                        new_taro -= stolen

                next_turn = 1 - turn
                res = dfs(na, nb, nc, nd, new_taro, new_jiro, next_turn)
                if turn == 0:
                    if res > best:
                        best = res
                else:
                    if res < best:
                        best = res

        return best

    result = dfs(n[0], n[1], n[2], n[3], 0, 0, 0)
    if result > 0:
        print("Taro")
    elif result < 0:
        print("Jiro")
    else:
        print("Draw")

if __name__ == "__main__":
    main()
0