AT_abc208_b [ABC208B] Factorial Yen Coin

题目描述

在高桥王国中，流通着 $1!$ 日元硬币、$2!$ 日元硬币、$\dots$、$10!$ 日元硬币。这里，$N! = 1 \times 2 \times \dots \times N$。

高桥君每种硬币各有 $100$ 枚，他想要购买价格为 $P$ 日元的商品，并且要求恰好支付，不找零。

在本题的限制条件下，可以证明一定存在满足条件的支付方式。

请问，最少需要使用多少枚硬币才能支付？

输入格式

输入从标准输入按以下格式给出。

$P$

输出格式

输出所需的最小硬币枚数。

输入输出样例 #1

输入 #1

9

输出 #1

3

输入输出样例 #2

输入 #2

119

输出 #2

10

输入输出样例 #3

输入 #3

10000000

输出 #3

24

说明/提示

限制

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

样例解释 1

使用 $1! = 1$ 日元硬币、$2! = 2$ 日元硬币、$3! = 6$ 日元硬币各 $1$ 枚，可以用 $3$ 枚硬币恰好支付 $9$ 日元的商品。不存在比这更少枚数的支付方式。

样例解释 2

可以使用 $1!$ 日元硬币 $1$ 枚、$2!$ 日元硬币 $2$ 枚、$3!$ 日元硬币 $3$ 枚、$4!$ 日元硬币 $4$ 枚来支付。

由 ChatGPT 4.1 翻译