#1055482 (PyPy3) No.288 貯金箱の仕事

• 問題: No.288 貯金箱の仕事
• ユーザー: lam6er
• 提出日時: 2025-03-20 20:21:49
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 4,343 bytes
• コンパイル時間: 265 ms
• コンパイル使用メモリ: 82,520 KB
• 実行使用メモリ: 77,180 KB
• 最終ジャッジ日時: 2025-03-20 20:24:18
• 合計ジャッジ時間: 15,852 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 33 WA * 20

ソースコード

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx +=2
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    K = list(map(int, input[idx:idx+N]))
    idx +=N

    # Check if the piggy bank has 1-yen coin
    has_1 = (A[0] == 1) if N >0 else False

    # Precompute the minimum coins required for the piggy bank to pay x yen
    # Here, using a BFS approach to compute minimal coins for x up to a certain limit
    max_A = A[-1]
    max_limit = max_A * 2

    from collections import deque
    visited = dict()
    q = deque()
    q.append((0,0))
    visited[0] = 0
    while q:
        current, coins = q.popleft()
        for a in A:
            next_val = current + a
            if next_val > max_limit:
                continue
            if next_val not in visited or visited[next_val] > coins + 1:
                visited[next_val] = coins + 1
                q.append((next_val, coins+1))
    # Function to compute minimal coins for x
    def minimal_coins(x):
        if x in visited:
            return visited[x]
        if not has_1:
            return -1
        # Compute with greedy approach since it has 1-yen coin
        res =0
        rem = x
        for a in reversed(A):
            if rem <=0:
                break
            if a ==1:
                res += rem
                rem =0
                break
            cnt = rem //a
            res += cnt
            rem -= cnt *a
        if rem ==0:
            return res
        else:
            return -1

    # Now, we need to check for possible x where:
    # - User can pay t = M+x
    # - Piggy can pay x
    # We'll try to compute for possible x in some range

    # For user to pay t, we need to find if possible and maximum coins sum_y
    # Which can be viewed as trying to use as many small coins as possible

    # Function to check if user can pay t and return the max coins count
    def user_max_coins(t):
        remaining = t
        total_coins =0
        # Use coins from smallest to largest
        for i in range(N):
            a = A[i]
            k = K[i]
            # Use as many as possible
            use = min(k, remaining //a)
            remaining -= use * a
            total_coins += use
            if remaining ==0:
                break
        if remaining !=0:
            return -1
        else:
            return total_coins

    # Since the piggy can pay any x if has_1, but we don't know user's payment
    # Let's search for possible t = M +x in the possible range

    max_possible = sum(A[i] * K[i] for i in range(N))
    if M > max_possible:
        print(-1)
        return

    best = None

    # Check x=0 first
    x =0
    t = M
    sum_z = minimal_coins(x)
    if sum_z !=0 and x !=0:
        pass
    else:
        sum_y = user_max_coins(t)
        if sum_y != -1:
            diff = sum_z - sum_y
            best = diff

    # Then check other possible x. How?
    # Another idea: x could be in the form of some coins in the piggy's set

    if has_1:
        # Piggy can pay any x, so we can iterate x as a possible value within a reasonable range
        # But M+x could be very big, how to limit the t?

        # Let's consider that for the user to pay t, the maximum sum_y is t (all 1's)
        # and the piggy's sum_z is the minimal coins for x = t-M

        # We can iterate t in [M, M + upper_bound], where upper_bound is like sum largest coins

        # Let's set upper_bound for t as up to M + max_A*N (arbitrary, but may cover possible optimal x)
        upper_t = M + 100000
        upper_t = min(upper_t, max_possible)
        for t in range(M, upper_t +1):
            if t > max_possible:
                break
            sum_y = user_max_coins(t)
            if sum_y == -1:
                continue
            x_candidate = t - M
            sum_z = minimal_coins(x_candidate)
            if sum_z == -1:
                continue
            current_diff = sum_z - sum_y
            if best is None or current_diff < best:
                best = current_diff

        if best is not None:
            total = sum(K) + best
            print(total)
            return
        else:
            print(-1)
            return
    else:
        print(-1)
        return

if __name__ == "__main__":
    main()