結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:50:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,878 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 852,372 KB
最終ジャッジ日時 2025-06-12 13:50:42
合計ジャッジ時間 5,473 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def can_pay(a1000, a100, a1, D):
    max_1000 = min(a1000, D // 1000)
    for used_1000 in range(max_1000, -1, -1):
        rem = D - used_1000 * 1000
        if rem < 0:
            continue
        max_100 = min(a100, rem // 100)
        for used_100 in range(max_100, -1, -1):
            rem2 = rem - used_100 * 100
            if rem2 < 0:
                continue
            if a1 >= rem2:
                return (used_1000, used_100, rem2)
    return None

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())
    
    queue = deque()
    initial_state = (A1000, A100, A1)
    queue.append((initial_state[0], initial_state[1], initial_state[2], 0))
    max_count = 0
    
    while queue:
        a1000, a100, a1, count = queue.popleft()
        if count > max_count:
            max_count = count
        
        # Try B
        payment = can_pay(a1000, a100, a1, Db)
        if payment is not None:
            used_1000, used_100, used_1 = payment
            new_1000 = a1000 - used_1000 + B1000
            new_100 = a100 - used_100 + B100
            new_1 = a1 - used_1 + B1
            if new_1000 >= 0 and new_100 >= 0 and new_1 >= 0:
                queue.append((new_1000, new_100, new_1, count + 1))
        
        # Try C
        payment = can_pay(a1000, a100, a1, Dc)
        if payment is not None:
            used_1000, used_100, used_1 = payment
            new_1000 = a1000 - used_1000 + C1000
            new_100 = a100 - used_100 + C100
            new_1 = a1 - used_1 + C1
            if new_1000 >= 0 and new_100 >= 0 and new_1 >= 0:
                queue.append((new_1000, new_100, new_1, count + 1))
    
    print(max_count)

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