結果

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

ソースコード

diff # 

def max_ouchi():
    import sys
    from collections import deque

    A_1000, A_100, A_1 = map(int, sys.stdin.readline().split())
    D_b = int(sys.stdin.readline())
    B = list(map(int, sys.stdin.readline().split()))
    D_c = int(sys.stdin.readline())
    C = list(map(int, sys.stdin.readline().split()))

    initial = (A_1000, A_100, A_1)
    visited = set()
    queue = deque()
    queue.append((initial[0], initial[1], initial[2], 0))
    visited.add((initial[0], initial[1], initial[2]))

    max_count = 0

    def get_total(a1000, a100, a1):
        return a1000 * 1000 + a100 * 100 + a1

    while queue:
        a1000, a100, a1, count = queue.popleft()
        current_total = get_total(a1000, a100, a1)
        if count > max_count:
            max_count = count

        if current_total < min(D_b, D_c):
            continue

        def try_pay_b(a1000, a100, a1):
            needed = D_b
            total = current_total
            if total < needed:
                return []
            p1000 = min(a1000, needed // 1000)
            needed -= p1000 * 1000
            p100 = min(a100, needed // 100)
            needed -= p100 * 100
            p1 = min(a1, needed)
            needed -= p1
            if needed != 0:
                return []
            new_a1000 = a1000 - p1000 + B[0]
            new_a100 = a100 - p100 + B[1]
            new_a1 = a1 - p1 + B[2]
            return (new_a1000, new_a100, new_a1)

        new_state = try_pay_b(a1000, a100, a1)
        if new_state:
            if (new_state[0], new_state[1], new_state[2]) not in visited:
                visited.add((new_state[0], new_state[1], new_state[2]))
                queue.append((new_state[0], new_state[1], new_state[2], count + 1))

        def try_pay_c(a1000, a100, a1):
            needed = D_c
            total = current_total
            if total < needed:
                return []
            p1000 = min(a1000, needed // 1000)
            needed -= p1000 * 1000
            p100 = min(a100, needed // 100)
            needed -= p100 * 100
            p1 = min(a1, needed)
            needed -= p1
            if needed != 0:
                return []
            new_a1000 = a1000 - p1000 + C[0]
            new_a100 = a100 - p100 + C[1]
            new_a1 = a1 - p1 + C[2]
            return (new_a1000, new_a100, new_a1)

        new_state = try_pay_c(a1000, a100, a1)
        if new_state:
            if (new_state[0], new_state[1], new_state[2]) not in visited:
                visited.add((new_state[0], new_state[1], new_state[2]))
                queue.append((new_state[0], new_state[1], new_state[2], count + 1))

    print(max_count)

max_ouchi()
0