/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 円硬貨を 1 枚ずつ使うと 3 枚の硬貨で 9 円の商品をちょうどの金額で支払うことができます。これより少ない枚数で支払う方法は存在しません。
入力例 2
119
出力例 2
10
1! 円硬貨を 1 枚、2! 円硬貨を 2 枚、3! 円硬貨を 3 枚、4! 円硬貨を 4 枚使えばよいです。
入力例 3
10000000
出力例 3
24
Score : 200 points
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