結果
| 問題 |
No.158 奇妙なお使い
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,520 bytes |
| コンパイル時間 | 429 ms |
| コンパイル使用メモリ | 82,512 KB |
| 実行使用メモリ | 285,724 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:03 |
| 合計ジャッジ時間 | 7,205 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 4 TLE * 1 -- * 22 |
ソースコード
import sys
# Set a higher recursion depth limit. The problem involves finding the longest path
# in a DAG, which could potentially be deep if the value decrease per errand is small.
# Python's default recursion limit (often 1000) might not be sufficient.
# We estimate the max possible errands could be up to 10000 (if initial value is 10000
# and each errand reduces value by 1). Setting limit to 20000 for safety.
try:
sys.setrecursionlimit(20000)
except Exception as e:
# In some environments (like restricted online judges), setting recursion limit might fail.
# The program will proceed with the default limit.
# We can print a warning for local debugging, but it's commented out for submission.
# print(f"Warning: Could not set recursion depth limit. {e}", file=sys.stderr)
pass
# Read initial holdings of A-kun: number of 1000-yen bills, 100-yen coins, and 1-yen coins.
A1000, A100, A1 = map(int, sys.stdin.readline().split())
# Read transaction details for visiting B-san: amount to pay (Db), and money received back.
Db = int(sys.stdin.readline())
B1000, B100, B1 = map(int, sys.stdin.readline().split())
# Read transaction details for visiting C-san: amount to pay (Dc), and money received back.
Dc = int(sys.stdin.readline())
C1000, C100, C1 = map(int, sys.stdin.readline().split())
# Memoization dictionary to store results for states already computed.
# Keys are tuples (a1000, a100, a1), values are the max number of errands from that state.
memo = {}
def solve(a1000, a100, a1):
"""
Recursive function with memoization to find the maximum number of errands
possible starting from the state (a1000, a100, a1).
"""
# Represent the state as a tuple to use as a dictionary key.
state = (a1000, a100, a1)
# Check if the result for this state is already in the memoization cache.
if state in memo:
return memo[state]
# Initialize the maximum number of further errands possible from this state.
max_errands = 0
# Calculate the total monetary value A-kun currently possesses.
current_value = a1000 * 1000 + a100 * 100 + a1
# --- Attempt to perform an errand by visiting B-san ---
# Check if A-kun has enough total value to potentially pay Db.
# Note: Having enough total value doesn't guarantee payment is possible with exact denominations.
if current_value >= Db:
# Use a set to store unique next states reachable by visiting B-san.
# This avoids redundant recursive calls for the same resulting state achieved via different payment combinations.
possible_next_states_B = set()
# Iterate through all possible numbers of 1000-yen bills (p1000) to use for payment.
# Cannot use more bills than available (a1000).
# Cannot use bills worth more than the required payment (Db // 1000).
max_p1000 = min(a1000, Db // 1000)
for p1000 in range(max_p1000 + 1):
# Calculate the remaining amount to be paid after using p1000 bills.
rem_Db = Db - p1000 * 1000
# Iterate through all possible numbers of 100-yen coins (p100) to use for payment.
# Cannot use more coins than available (a100).
# Cannot use coins worth more than the remaining amount (rem_Db // 100).
max_p100 = min(a100, rem_Db // 100)
for p100 in range(max_p100 + 1):
# Calculate the final remaining amount after using p100 coins.
# This amount must be paid exactly using 1-yen coins (p1).
p1 = rem_Db - p100 * 100
# The required number of 1-yen coins (p1) must be non-negative. This is guaranteed
# by the loop range for p100, which ensures p100 * 100 <= rem_Db.
# Check if A-kun has enough 1-yen coins (a1) to pay p1.
if p1 <= a1:
# If yes, this combination (p1000, p100, p1) is a valid way to pay Db.
# Calculate the state after payment and receiving money back from B-san.
next_a1000 = a1000 - p1000 + B1000
next_a100 = a100 - p100 + B100
next_a1 = a1 - p1 + B1
# Add the resulting state to the set of possible next states.
possible_next_states_B.add((next_a1000, next_a100, next_a1))
# After finding all possible payment combinations and resulting states for B-san,
# explore each unique next state recursively.
for next_state in possible_next_states_B:
# The total number of errands for this path is 1 (the current errand to B)
# plus the maximum number of errands possible from the next state.
# Update max_errands if this path yields more errands than previously found.
max_errands = max(max_errands, 1 + solve(next_state[0], next_state[1], next_state[2]))
# --- Attempt to perform an errand by visiting C-san ---
# The logic is identical to visiting B-san, just using Dc and C's received amounts.
if current_value >= Dc:
possible_next_states_C = set()
max_q1000 = min(a1000, Dc // 1000)
for q1000 in range(max_q1000 + 1):
rem_Dc = Dc - q1000 * 1000
max_q100 = min(a100, rem_Dc // 100)
for q100 in range(max_q100 + 1):
q1 = rem_Dc - q100 * 100
# Check if enough 1-yen coins are available. q1 >= 0 is guaranteed.
if q1 <= a1:
next_a1000 = a1000 - q1000 + C1000
next_a100 = a100 - q100 + C100
next_a1 = a1 - q1 + C1
possible_next_states_C.add((next_a1000, next_a100, next_a1))
# Explore each unique next state reachable via C
for next_state in possible_next_states_C:
# Update max_errands if visiting C leads to a longer path of errands.
max_errands = max(max_errands, 1 + solve(next_state[0], next_state[1], next_state[2]))
# Store the computed maximum number of errands for the current state in the cache.
memo[state] = max_errands
# Return the result for this state.
return max_errands
# Start the recursive process from the initial state (A1000, A100, A1).
result = solve(A1000, A100, A1)
# Print the final result, which is the maximum total number of errands A-kun can perform.
print(result)