-
Notifications
You must be signed in to change notification settings - Fork 0
/
ABC_208_B.cpp
70 lines (53 loc) · 1.23 KB
/
ABC_208_B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Task->Factorial Yen Coin.
//HINT 1-> Coin Change Problem Variation (Greedy Algorithms)
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
#define rep(i,n,s) for(int i=0;i<n;i+=s)
#define mxsize 100000
using namespace std;
//Hint 2-> Use concept of Coin Change Problem but instead of coins use factorials of that each coin.
NOTE-->//Beware of Overflow & Out of Range Errors .Because Factorials can be pretty large-[Check Constraints of the problem]
//Hint 3->To Avoid TLE & Overflows Precalculate Factrials of some numbers & store in an array.
//[Wiseky choose the range to which you should precalculate based on constraints of the problem.
int fact(int n)
{
int fact = 1;
for (int i = 2; i <= n; i++)
{
fact *= i;
}
return fact;
}
int fa[13];
void s2()
{
for (int i = 0; i < 13; i++) {
fa[i] = fact(i);
}
int p, ans = 0;
cin >> p;
while (p > 0) {
int i = 0;
for (; i < 13; i++)
{
if (fa[i] > p)break;
}
i--;
int k = p / fa[i];
ans += k;
p = p - (k * fa[i]);
}
cout << ans << endl;
//Just debugging.
// cout << fa[12] << endl;
// for (int i = 0; i < 13; i++) {
// cout << fa[i] << " ";
// }
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
s2();
}