結果

問題 No.158 奇妙なお使い
ユーザー gew1fw
提出日時 2025-06-12 18:51:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,080 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 79,424 KB
最終ジャッジ日時 2025-06-12 18:52:05
合計ジャッジ時間 3,138 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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

    B_return = B1000 * 1000 + B100 * 100 + B1
    C_return = C1000 * 1000 + C100 * 100 + C1

    def generate_payments(current_a1000, current_a100, current_a1, D):
        payments = []
        max_x = min(current_a1000, D // 1000)
        for x in range(max_x + 1):
            rem = D - x * 1000
            if rem < 0:
                continue
            max_y = min(current_a100, rem // 100)
            for y in range(max_y + 1):
                rem2 = rem - y * 100
                if rem2 < 0:
                    continue
                if rem2 <= current_a1:
                    z = rem2
                    payments.append((x, y, z))
        return payments

    visited = {}
    max_count = 0

    initial_s = a1000 * 1000 + a100 * 100 + a1
    queue = deque()
    queue.append((a1000, a100, a1, 0))
    visited[initial_s] = (a1000, a100, a1)

    while queue:
        a1k, a100_, a1_, cnt = queue.popleft()
        max_count = max(max_count, cnt)

        current_s = a1k * 1000 + a100_ * 100 + a1_

        for target in ['B', 'C']:
            if target == 'B':
                D = Db
                ret_1k = B1000
                ret_100 = B100
                ret_1 = B1
                ret_total = B_return
            else:
                D = Dc
                ret_1k = C1000
                ret_100 = C100
                ret_1 = C1
                ret_total = C_return

            if current_s < D:
                continue

            payments = generate_payments(a1k, a100_, a1_, D)
            for x, y, z in payments:
                new_1k = a1k - x + ret_1k
                new_100 = a100_ - y + ret_100
                new_1 = a1_ - z + ret_1

                if new_1k < 0 or new_100 < 0 or new_1 < 0:
                    continue

                new_s = new_1k * 1000 + new_100 * 100 + new_1
                if new_s <= 0:
                    continue

                if new_s not in visited:
                    visited[new_s] = (new_1k, new_100, new_1)
                    queue.append((new_1k, new_100, new_1, cnt + 1))
                else:
                    existing_1k, existing_100, existing_1 = visited[new_s]
                    if (new_1k > existing_1k or
                        (new_1k == existing_1k and new_100 > existing_100) or
                        (new_1k == existing_1k and new_100 == existing_100 and new_1 > existing_1)):
                        visited[new_s] = (new_1k, new_100, new_1)
                        queue.append((new_1k, new_100, new_1, cnt + 1))

    print(max_count)

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