分数: 200 点
问题陈述
高桥王国使用的硬币是 1!-日元硬币, 2!-日元硬币, \dots,和 10!- 日元硬币。在这里, N! = 1 \times 2 \times \dots \times N.
高桥有 100 的各种硬币,他将购买一个值得的产品 P 日元 提供准确的金额而不收到找零.
我们可以证明,总有这样的支付方式。
他的付款至少需要使用多少个硬币?
约束
- 1 \leq P \leq 10^7
- P 是一个整数。
输入
输入由标准输入按以下格式给出:
P
输出
打印所需的最少硬币数量。
样本输入 1
9
示例输出 1
3
通过给予一个 (1! =) 1-日元硬币,一枚 (2! =) 2-日元硬币和一枚 (3! =) 6-日元硬币,我们可以准确支付产品价值 9 日元。无法使用更少的硬币来支付这笔金额。
示例输入 2
119
示例输出 2
10
我们应该使用一个 1!-日元硬币,两枚 2!-日元硬币,三枚 3!-日元硬币和四个 4!- 日元硬币。
示例输入 3
10000000
示例输出 3
24