【pythonでABC208を解説】B - Factorial Yen Coin

問題概要

問題ページ

B - Factorial Yen Coin

問題ページへ移動する

問題文

高橋王国では \(1!\) 円硬貨 \(, 2!\) 円硬貨 \(, \dots, 10!\) 円硬貨が流通しています。ここで、\(N! = 1 \times 2 \times \dots \times N\) です。

高橋君は全ての種類の硬貨を \(100\) 枚ずつ持っており、\(P\) 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。

問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。

最小で何枚の硬貨を使えば支払うことができますか？

制約

• \(1 \leq P \leq 10^7\)
• \(P\) は整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    p = int(input().rstrip('\n'))
    f = [1]
    for i in range(2, 11):
        f.append(f[-1] * i)
    total = 0
    for i in range(9, -1, -1):
        dv, md = divmod(p, f[i])
        if dv != 0:
            total += dv
            p = md
    print(total)


if __name__ == '__main__':
    solve()