Score : $200$ points

问题描述

在高桥王国中使用的硬币是$1!$-yen硬币、$2!$-yen硬币、$\dots$以及$10!$-yen硬币。这里，$N! = 1 \times 2 \times \dots \times N$。

高桥拥有每种面额的硬币各100枚，他打算购买一件价值为$P$日元的产品，并准确支付，无需找零。

我们可以证明总是存在一种这样的支付方式。

在他的支付中至少需要使用多少枚硬币？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The coins used in the Kingdom of Takahashi are $1!$-yen coins, $2!$-yen coins, $\dots$, and $10!$-yen coins. Here, $N! = 1 \times 2 \times \dots \times N$.

Takahashi has $100$ of every kind of coin, and he is going to buy a product worth $P$ yen by giving the exact amount without receiving change.

We can prove that there is always such a way to make payment.

At least how many coins does he need to use in his payment?

Constraints

• $1 \leq P \leq 10^7$
• $P$ is an integer.

Input

Input is given from Standard Input in the following format:

$P$

Output

Print the minimum number of coins needed.

Sample Input 1

9

Sample Output 1

3

By giving one $(1! =) 1$-yen coin, one $(2! =) 2$-yen coin, and one $(3! =) 6$-yen coin, we can make the exact payment for the product worth $9$ yen. There is no way to pay this amount using fewer coins.

Sample Input 2

119

Sample Output 2

10

We should use one $1!$-yen coin, two $2!$-yen coins, three $3!$-yen coins, and four $4!$-yen coins.

Sample Input 3

10000000

Sample Output 3

24

update @ 2024/3/10 09:21:32