結果

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

ソースコード

diff # 

from collections import deque

def main():
    a1000, a100, a1 = map(int, input().split())
    Db = int(input())
    B = list(map(int, input().split()))
    Dc = int(input())
    C = list(map(int, input().split()))
    
    Br = (B[0], B[1], B[2])
    Cr = (C[0], C[1], C[2])
    
    visited = set()
    q = deque()
    initial_state = (a1000, a100, a1)
    q.append((a1000, a100, a1, 0))
    visited.add(initial_state)
    
    max_count = 0
    
    while q:
        current = q.popleft()
        a1k, a100_, a1_, count = current
        max_count = max(max_count, count)
        
        # Try B's operation
        can_b = False
        for x in range(min(a1k, Db // 1000) + 1):
            remaining = Db - x * 1000
            if remaining < 0:
                continue
            max_y = min(a100_, remaining // 100)
            for y in range(max_y, -1, -1):
                z = remaining - y * 100
                if z >= 0 and z <= a1_:
                    new_a1k = a1k - x + Br[0]
                    new_a100 = a100_ - y + Br[1]
                    new_a1 = a1_ - z + Br[2]
                    new_state = (new_a1k, new_a100, new_a1)
                    if new_state not in visited:
                        visited.add(new_state)
                        q.append((new_a1k, new_a100, new_a1, count + 1))
                    can_b = True
                    break
            if can_b:
                break
        
        # Try C's operation
        can_c = False
        for x in range(min(a1k, Dc // 1000) + 1):
            remaining = Dc - x * 1000
            if remaining < 0:
                continue
            max_y = min(a100_, remaining // 100)
            for y in range(max_y, -1, -1):
                z = remaining - y * 100
                if z >= 0 and z <= a1_:
                    new_a1k = a1k - x + Cr[0]
                    new_a100 = a100_ - y + Cr[1]
                    new_a1 = a1_ - z + Cr[2]
                    new_state = (new_a1k, new_a100, new_a1)
                    if new_state not in visited:
                        visited.add(new_state)
                        q.append((new_a1k, new_a100, new_a1, count + 1))
                    can_c = True
                    break
            if can_c:
                break
    
    print(max_count)

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