結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:01:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,312 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 275,192 KB
最終ジャッジ日時 2025-04-16 16:07:38
合計ジャッジ時間 7,226 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

# Read input
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())

max_steps = {}
queue = deque()

initial_state = (A1000, A100, A1)
max_steps[initial_state] = 0
queue.append((A1000, A100, A1, 0))

max_result = 0

while queue:
    a, b, c, steps = queue.popleft()
    if steps > max_result:
        max_result = steps

    # Try B transaction
    required = Db
    max_x = min(a, required // 1000)
    for x in range(max_x + 1):
        rem = required - x * 1000
        if rem < 0:
            continue
        max_y = min(b, rem // 100)
        for y in range(max_y + 1):
            rem2 = rem - y * 100
            z = rem2
            if z < 0 or z > c:
                continue
            # Calculate new state after paying and receiving B's coins
            new_a_b = a - x + B1000
            new_b_b = b - y + B100
            new_c_b = c - z + B1
            if new_a_b < 0 or new_b_b < 0 or new_c_b < 0:
                continue
            new_state = (new_a_b, new_b_b, new_c_b)
            new_steps = steps + 1
            if new_state not in max_steps or new_steps > max_steps.get(new_state, -1):
                max_steps[new_state] = new_steps
                queue.append((new_a_b, new_b_b, new_c_b, new_steps))

    # Try C transaction
    required = Dc
    max_x = min(a, required // 1000)
    for x in range(max_x + 1):
        rem = required - x * 1000
        if rem < 0:
            continue
        max_y = min(b, rem // 100)
        for y in range(max_y + 1):
            rem2 = rem - y * 100
            z = rem2
            if z < 0 or z > c:
                continue
            # Calculate new state after paying and receiving C's coins
            new_a_c = a - x + C1000
            new_b_c = b - y + C100
            new_c_c = c - z + C1
            if new_a_c < 0 or new_b_c < 0 or new_c_c < 0:
                continue
            new_state = (new_a_c, new_b_c, new_c_c)
            new_steps = steps + 1
            if new_state not in max_steps or new_steps > max_steps.get(new_state, -1):
                max_steps[new_state] = new_steps
                queue.append((new_a_c, new_b_c, new_c_c, new_steps))

print(max_result)
0