暑期训练2：AtCoder Beginner Contest 208 B - Factorial Yen Coin

B - Factorial Yen Coin
Time Limit: 2 sec Memory Limit: 1024 MB

Score :
200
points

Problem Statement
The coins used in the Kingdom of Takahashi are
1
!
-yen coins,
2
!
-yen coins,
…
, and
10
!
-yen coins. Here,
N
!

1
×
2
×
⋯
×
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
≤
P
≤
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
Copy
9
Sample Output 1
Copy
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
Copy
119
Sample Output 2
Copy
10
We should use one
1
!
-yen coin, two
2
!
-yen coins, three
3
!
-yen coins, and four
4
!
-yen coins.

Sample Input 3
Copy
10000000
Sample Output 3
Copy
24
题解：本题就是相当于简单的背包问题，我们用一个数组对于各种阶乘的值进行相关的保存，此时就是利用简单的贪心思想进行相关的组合数的值的挑选即可，利用ans进行相关的数目统计即可完成本题的解答。

#include
using namespace std;
long long f[22]={1,1}; 
int main()
{for(long long i=2;i<=10;i++)f[i]=f[i-1]*i;long long n;cin>>n;int now=10;int ans=0;for(;;){while(f[now]>n) --now;ans+=n/f[now];n%=f[now];--now;if(n==0)break;}cout<<ans<<endl;return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！