結果
| 問題 |
No.288 貯金箱の仕事
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:03:42 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,220 bytes |
| コンパイル時間 | 435 ms |
| コンパイル使用メモリ | 82,664 KB |
| 実行使用メモリ | 83,712 KB |
| 最終ジャッジ日時 | 2025-05-14 13:05:34 |
| 合計ジャッジ時間 | 26,232 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 48 WA * 2 TLE * 3 |
ソースコード
import heapq
import math
import sys
# Use fast I/O
input = sys.stdin.readline
def solve():
# Read input values N and M
N, M_str = input().split()
N = int(N)
M = int(M_str) # M can be large, up to 10^18
# Read coin denominations A_1, ..., A_N
A_str = input().split()
A = [int(a) for a in A_str] # A_i up to 500
# Read initial coin counts K_1, ..., K_N
K_str = input().split()
K = [int(k) for k in K_str] # K_i up to 10^12
# Calculate the total value Yukiusagi initially possesses
current_total_value = 0
for i in range(N):
# Calculations involve large integers, Python handles this automatically
current_total_value += K[i] * A[i]
# The problem transforms into a change-making problem.
# We need to find the minimum number of coins to make change for value M' = sum(K_i A_i) - M.
# Let target_val = M'.
target_val = current_total_value - M
# If target_val is negative, it means Yukiusagi doesn't have enough value M to begin with.
# The transaction is impossible.
if target_val < 0:
print("-1")
return
# If target_val is zero, it means Yukiusagi has exactly M value more than needed.
# She pays M, using all her coins? No, she needs to pay exactly M net.
# If target_val = 0, this means sum K_i A_i = M. Yukiusagi can pay M using all her coins.
# In the transformed problem, we need to make change for M'=0. Minimum coins is 0.
if target_val == 0:
print("0")
return
# Calculate the greatest common divisor (GCD) of all coin denominations.
g = A[0]
for i in range(1, N):
g = math.gcd(g, A[i])
# The net amount M must be payable. Any payable amount must be a multiple of the GCD.
# If M is not divisible by g, the transaction is impossible.
if M % g != 0:
print("-1")
return
# Also, the target value M' must be formable using the available coins.
# This implies M' must also be divisible by g.
# Check: M' = sum K_i A_i - M. Since each A_i is divisible by g, sum K_i A_i is divisible by g.
# If M is divisible by g, then M' = (multiple of g) - (multiple of g), which is also a multiple of g.
# If M is not divisible by g, then M' = (multiple of g) - (not multiple of g), which is not multiple of g.
# So the check M % g != 0 already covers the condition for M'. We add an explicit check for safety.
if target_val % g != 0:
print("-1")
return
# Use the largest coin denomination A_N as the base for the Dijkstra algorithm modulus.
# The problem states A is sorted: A_1 < A_2 < ... < A_N.
A_N = A[N-1]
# For the change-making problem (minimum coins for target_val), we use a hybrid approach:
# 1. Standard dynamic programming for small target values.
# 2. Dijkstra on remainders modulo A_N for large target values.
# Define a bound B to switch between DP and Dijkstra. A safe bound is related to A_N^2.
# Let's use B = 2 * A_N^2.
max_A = A_N
# The bound calculation can result in a large number, Python handles this.
bound_B = 2 * max_A * max_A
# Handle the edge case N=1 separately.
if N == 1:
# Only one type of coin A[0]. Change making is simple division.
if target_val % A[0] == 0:
# Result is target_val / A[0] coins.
print(target_val // A[0])
else:
# Cannot make exact change.
print("-1")
return
# Use float('inf') for representing infinity. Comparisons work correctly with large integers.
INF = float('inf')
# If target_val is small (<= bound_B), use DP.
if target_val <= bound_B:
# `target_val` can be large, ensure `dp_limit` fits standard integer range if needed.
# In Python, list indexing with large integers is okay.
dp_limit = int(target_val)
dp_small = [INF] * (dp_limit + 1)
dp_small[0] = 0 # Base case: 0 value requires 0 coins.
# Fill DP table
for v in range(1, dp_limit + 1):
for coin in A: # Iterate through available coin denominations
if v >= coin and dp_small[v - coin] != INF:
# Update minimum coins needed for value v
dp_small[v] = min(dp_small[v], 1 + dp_small[v - coin])
final_coins = dp_small[dp_limit]
if final_coins == INF:
# target_val cannot be formed.
print("-1")
else:
# Print the minimum number of coins found by DP.
print(int(final_coins)) # Ensure output is integer
return
# If target_val is large (> bound_B), use Dijkstra on remainders modulo A_N.
# `min_cost_for_rem[r]` stores the minimum number of coins found so far for *some* value V s.t. V % A_N == r.
# `min_val_at_min_cost[r]` stores the minimum value V that achieved this minimum cost.
min_cost_for_rem = {}
min_val_at_min_cost = {}
# Initialize distances/costs to infinity for all remainders.
for r in range(A_N):
min_cost_for_rem[r] = INF
min_val_at_min_cost[r] = INF
# Initialize state for remainder 0: 0 cost, 0 value.
min_cost_for_rem[0] = 0
min_val_at_min_cost[0] = 0
# Priority queue for Dijkstra. Stores tuples: (cost, value, remainder).
# Python's heapq implements a min-heap.
pq_actual = [(0, 0, 0)]
while pq_actual:
# Pop the state with the lexicographically smallest (cost, value) pair.
cost, value, rem = heapq.heappop(pq_actual)
# If we've found a better path to this remainder state already, skip.
if cost > min_cost_for_rem[rem] or (cost == min_cost_for_rem[rem] and value > min_val_at_min_cost[rem]):
continue
# Explore neighbors by trying to add each coin type.
for i in range(N):
curr_A = A[i]
# Calculate next state's remainder, cost, and value.
next_rem = (rem + curr_A) % A_N
next_cost = cost + 1
next_value = value + curr_A
# If this path leads to a better state (lexicographically smaller cost, value pair)
# for `next_rem`, update and push to priority queue.
if next_cost < min_cost_for_rem[next_rem] or \
(next_cost == min_cost_for_rem[next_rem] and next_value < min_val_at_min_cost[next_rem]):
min_cost_for_rem[next_rem] = next_cost
min_val_at_min_cost[next_rem] = next_value
heapq.heappush(pq_actual, (next_cost, next_value, next_rem))
# After Dijkstra, find the result for target_val based on its remainder.
target_rem = target_val % A_N
# Check if the target remainder is reachable.
if min_cost_for_rem[target_rem] == INF:
# If unreachable, target_val cannot be formed.
print("-1")
return
# Get the base cost and base value found by Dijkstra for target_rem.
base_cost = min_cost_for_rem[target_rem]
base_val = min_val_at_min_cost[target_rem]
# Critical check: target_val must be at least the minimum value found for its remainder path.
# If target_val < base_val, it means target_val cannot be formed by adding A_N coins
# to the base value `base_val`. Based on theory, this implies impossibility for large values.
if target_val < base_val:
print("-1")
return
# Calculate the difference that needs to be covered by A_N coins.
diff = target_val - base_val
# Safety check: The difference must be non-negative and divisible by A_N.
# This should hold true based on the logic, but check for robustness.
if diff < 0 or diff % A_N != 0:
# This indicates an unexpected state or logical error. Output -1 for impossibility.
print("-1")
return
# Calculate the number of A_N coins needed.
num_AN_coins = diff // A_N
# Total minimum coins = base cost from Dijkstra + number of A_N coins.
total_coins = base_cost + num_AN_coins
# Print the final result.
print(int(total_coins)) # Ensure output is integer
# Execute the solve function
solve()