結果

問題 No.158 奇妙なお使い
ユーザー lam6er
提出日時 2025-04-16 16:07:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,098 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 81,676 KB
実行使用メモリ 287,716 KB
最終ジャッジ日時 2025-04-16 16:14:54
合計ジャッジ時間 7,370 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    A1000, A100, A1 = map(int, input().split())
    Db = int(input())
    B1000, B100, B1 = map(int, input().split())
    Dc = int(input())
    C1000, C100, C1 = map(int, input().split())

    visited = {}
    heap = []
    initial_state = (A1000, A100, A1)
    heapq.heappush(heap, (0, A1000, A100, A1))
    visited[initial_state] = 0
    max_steps = 0

    while heap:
        current_neg_steps, a1000, a100, a1 = heapq.heappop(heap)
        current_steps = -current_neg_steps

        if current_steps < visited.get((a1000, a100, a1), -1):
            continue

        if current_steps > max_steps:
            max_steps = current_steps

        for target in ['B', 'C']:
            if target == 'B':
                D = Db
                get_coins = (B1000, B100, B1)
            else:
                D = Dc
                get_coins = (C1000, C100, C1)

            max_x = min(a1000, D // 1000)
            for x in range(0, max_x + 1):
                remaining = D - x * 1000
                if remaining < 0:
                    continue
                max_y = min(a100, remaining // 100)
                for y in range(0, max_y + 1):
                    rem2 = remaining - y * 100
                    if rem2 < 0:
                        continue
                    z = rem2
                    if z > a1:
                        continue

                    new_a1000 = a1000 - x + get_coins[0]
                    new_a100 = a100 - y + get_coins[1]
                    new_a1 = a1 - z + get_coins[2]

                    if new_a1000 < 0 or new_a100 < 0 or new_a1 < 0:
                        continue

                    new_steps = current_steps + 1
                    new_state = (new_a1000, new_a100, new_a1)

                    if new_state in visited:
                        if visited[new_state] >= new_steps:
                            continue
                    visited[new_state] = new_steps
                    heapq.heappush(heap, (-new_steps, new_a1000, new_a100, new_a1))

    print(max_steps)

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