← 返回题目列表

AtCoder · abc208_b

B. 阶乘日元硬币

中文机器翻译题面 查看原题

分数: 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