結果

問題 No.158 奇妙なお使い
ユーザー gew1fw
提出日時 2025-06-12 18:59:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,446 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 284,664 KB
最終ジャッジ日時 2025-06-12 18:59:26
合計ジャッジ時間 7,380 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 3 WA * 1 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0

    A1000 = int(input[idx]); idx +=1
    A100 = int(input[idx]); idx +=1
    A1 = int(input[idx]); idx +=1

    Db = int(input[idx]); idx +=1

    B1000 = int(input[idx]); idx +=1
    B100 = int(input[idx]); idx +=1
    B1 = int(input[idx]); idx +=1

    Dc = int(input[idx]); idx +=1

    C1000 = int(input[idx]); idx +=1
    C100 = int(input[idx]); idx +=1
    C1 = int(input[idx]); idx +=1

    queue = deque()
    initial_state = (A1000, A100, A1)
    queue.append( (A1000, A100, A1, 0) )
    visited = set()
    visited.add( (A1000, A100, A1) )

    max_steps = 0

    while queue:
        a1000, a100, a1, steps = queue.popleft()
        if steps > max_steps:
            max_steps = steps

        # Try B transaction
        max_x_b = min(a1000, Db // 1000)
        for x in range(max_x_b + 1):
            rem_x = Db - x * 1000
            if rem_x < 0:
                continue
            max_y_b = min(a100, rem_x // 100)
            for y in range(max_y_b + 1):
                rem_y = rem_x - y * 100
                if rem_y < 0:
                    continue
                if a1 >= rem_y:
                    new_a1000 = a1000 - x + B1000
                    new_a100 = a100 - y + B100
                    new_a1 = a1 - rem_y + B1
                    new_state = (new_a1000, new_a100, new_a1)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append( (new_a1000, new_a100, new_a1, steps + 1) )

        # Try C transaction
        max_x_c = min(a1000, Dc // 1000)
        for x in range(max_x_c + 1):
            rem_x = Dc - x * 1000
            if rem_x < 0:
                continue
            max_y_c = min(a100, rem_x // 100)
            for y in range(max_y_c + 1):
                rem_y = rem_x - y * 100
                if rem_y < 0:
                    continue
                if a1 >= rem_y:
                    new_a1000 = a1000 - x + C1000
                    new_a100 = a100 - y + C100
                    new_a1 = a1 - rem_y + C1
                    new_state = (new_a1000, new_a100, new_a1)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append( (new_a1000, new_a100, new_a1, steps + 1) )

    print(max_steps)

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