結果

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

ソースコード

diff # 

from collections import deque
import sys

def main():
    # Read input
    a1000, a100, a1 = map(int, sys.stdin.readline().split())
    D_b = int(sys.stdin.readline())
    B1000, B100, B1 = map(int, sys.stdin.readline().split())
    D_c = int(sys.stdin.readline())
    C1000, C100, C1 = map(int, sys.stdin.readline().split())

    initial_state = (a1000, a100, a1)
    steps_dict = {initial_state: 0}
    queue = deque([initial_state])
    max_steps = 0

    def get_possible_payments(current_a, current_b, current_c, D):
        possible = []
        max_x = min(current_a, D // 1000)
        for x in range(0, max_x + 1):
            rem = D - x * 1000
            if rem < 0:
                continue
            max_y = min(current_b, rem // 100)
            for y in range(0, max_y + 1):
                rem_y = rem - y * 100
                if rem_y < 0:
                    continue
                if rem_y <= current_c:
                    possible.append((x, y, rem_y))
        return possible

    while queue:
        current = queue.popleft()
        current_steps = steps_dict[current]

        if current_steps > max_steps:
            max_steps = current_steps

        current_a, current_b, current_c = current

        # Process B-san
        possible_B = get_possible_payments(current_a, current_b, current_c, D_b)
        for x, y, z in possible_B:
            new_a = current_a - x + B1000
            new_b = current_b - y + B100
            new_c = current_c - z + B1
            if new_a < 0 or new_b < 0 or new_c < 0:
                continue
            new_state = (new_a, new_b, new_c)
            new_step = current_steps + 1
            if new_state not in steps_dict or steps_dict[new_state] < new_step:
                steps_dict[new_state] = new_step
                queue.append(new_state)
                if new_step > max_steps:
                    max_steps = new_step

        # Process C-san
        possible_C = get_possible_payments(current_a, current_b, current_c, D_c)
        for x, y, z in possible_C:
            new_a = current_a - x + C1000
            new_b = current_b - y + C100
            new_c = current_c - z + C1
            if new_a < 0 or new_b < 0 or new_c < 0:
                continue
            new_state = (new_a, new_b, new_c)
            new_step = current_steps + 1
            if new_state not in steps_dict or steps_dict[new_state] < new_step:
                steps_dict[new_state] = new_step
                queue.append(new_state)
                if new_step > max_steps:
                    max_steps = new_step

    print(max_steps)

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