結果

問題 No.636 硬貨の枚数2
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:51:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 1,655 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 77,552 KB
最終ジャッジ日時 2025-03-31 17:52:48
合計ジャッジ時間 6,382 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    n = sys.stdin.readline().strip()
    n_digits = list(map(int, reversed(n)))  # Reverse the digits for processing
    max_k = len(n_digits) + 1
    current_dp = {0: 0}  # Maps borrow_in to minimal cost

    for k in range(max_k):
        next_dp = defaultdict(lambda: float('inf'))
        for borrow_in, cost in current_dp.items():
            for x_k in range(10):
                # Determine n_k for this digit
                if k < len(n_digits):
                    n_k = n_digits[k]
                else:
                    n_k = 0
                # Compute borrow_out and b_k
                if x_k - borrow_in >= n_k:
                    borrow_out = 0
                    b_k = x_k - borrow_in - n_k
                else:
                    borrow_out = 1
                    b_k = x_k - borrow_in - n_k + 10
                # Check if it's the last digit and enforce no borrow
                if k == max_k - 1 and borrow_out != 0:
                    continue
                # Calculate the costs for this digit
                f_cost = (x_k // 5) + (x_k % 5)
                g_cost = (b_k // 5) + (b_k % 5)
                total_cost = cost + f_cost + g_cost
                # Update the next_dp
                if total_cost < next_dp[borrow_out]:
                    next_dp[borrow_out] = total_cost
        current_dp = next_dp
        if not current_dp:
            break  # No valid states left

    # The valid answer is the state with borrow_in 0 after all digits processed
    ans = current_dp.get(0, float('inf'))
    print(ans)

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