B - 阶乘日元硬币

得分: $200$ 分

问题描述

在高桥王国中，使用的硬币有 $1!$-日元硬币，$2!$-日元硬币，直到 $10!$-日元硬币。这里，$N! = 1 \times 2 \times \dots \times N$。

高桥有每种硬币 $100$ 枚，他要用给定的 $P$ 日元购买一件商品 用刚好的金额付款，不需要找零。

我们可以证明总能找到这样的付款方式。

他至少需要使用多少个硬币进行付款？

约束

• $1 \leq P \leq 10^7$
• $P$ 是一个整数。

输入

从标准输入读入的格式如下：

$P$

输出

打印所需的最少硬币数量。

9

3

通过给出一个 $(1! =) 1$-日元硬币，一个 $(2! =) 2$-日元硬币，和一个 $(3! =) 6$-日元硬币，我们可以准确地支付价值为 $9$ 日元的商品。没有办法使用更少的硬币进行支付。

119

10

我们应该使用一个 $1!$-日元硬币，两个 $2!$-日元硬币，三个 $3!$-日元硬币，和四个 $4!$-日元硬币。

10000000

24

我们应该使用八个 $4!$-日元硬币，两个 $3!$-日元硬币，四个 $2!$-日元硬币，和十个 $1!$-日元硬币。