Factorial Yen Coin

题目描述

在高桥王国使用的硬币是 $1!$ 日元、 $2!$ 日元、 $\dots$ 和 $10!$ 日元。这里，$N! = 1 \times 2 \times \dots \times N$。 高桥每种硬币都有 $100$ 枚，他要用不找零、恰好付清的方式购买一件价值 $P$ 日元的商品。 我们可以证明总有办法凑出该金额。 至少需要使用多少枚硬币来支付？

输入格式

输入按以下格式由标准输入给出： $P$

输出格式

输出最少需要的硬币枚数。

9

3

119

10

10000000

24

提示

$1 \leq P \leq 10^7$ $P$ 是整数。通过给出一枚 $(1! =) 1$ 日元硬币、一枚 $(2! =) 2$ 日元硬币和一枚 $(3! =) 6$ 日元硬币，我们可以恰好支付价值 $9$ 日元的商品。无法用更少的硬币支付该金额。
我们应该使用一枚 $1!$ 日元硬币、两枚 $2!$ 日元硬币、三枚 $3!$ 日元硬币和四枚 $4!$ 日元硬币。

标签: AtCoder|abc208B

来源

AtCoder|abc208B