-
Notifications
You must be signed in to change notification settings - Fork 0
/
10223 - How many nodes.cpp
120 lines (95 loc) · 2.75 KB
/
10223 - How many nodes.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
#define si(x) scanf("%d",&x)
#define sii(x,y) scanf("%d %d",&x,&y)
#define siii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld %lld",&x,&y)
#define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define ss(ch) scanf("%s",ch)
#define pi(x) printf("%d",x)
#define pii(x,y) printf("%d %d",x,y)
#define pl(x) printf("%lld",x)
#define pll(x,y) printf("%lld %lld",x,y)
#define sf scanf
#define pf printf
#define pcs(x,y) printf("Case %d: %s", x, y)
#define pci(x,y) printf("Case %d: %d", x, y)
#define pcl(x,y) printf("Case %d: %lld", x, y)
#define NL printf("\n")
#define nl '\n'
#define mod 1000000007
#define FI freopen("in.txt","r",stdin)
#define FO freopen("out.txt","w",stdout)
#define FOR(i,j,k) for(int i = j; i < k; i++)
#define rep(l,n) FOR(l,0,n)
#define per(i,j,k) for(int i = j; i > k; i--)
#define PI acos(-1.0)
#define eps 1e-9
#define pb(x) push_back(x)
#define ppb() pop_back()
#define sz(x) x.size()
#define xx first
#define yy second
#define mp(a,b) make_pair(a,b)
#define ssz(a) strlen(a)
#define mem(ara,val) memset(ara,val,sizeof(ara))
#define clr(ara) mem(ara,0)
#define st(ara) mem(ara,-1)
#define all(a) a.begin(),a.end()
//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#define debug(args...) {dbg,args; cerr<<endl;}
struct debugger{
template<typename T> debugger& operator , (const T& v){
cout<<v<<" ";
return *this;
}
}dbg;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> PII;
typedef vector< PII > VII;
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};
///=>=>=>=>=>=>=>=>=>00100<=<=<=<=<=<=<=<=<=///
LL cat[50];
LL binomialCoeff(LL n, LL k){
LL res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for(int i = 0; i < k; ++i){
res *= (n - i);
res /= (i + 1);
}
return res;
}
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
LL catalan(LL n){
// Calculate value of 2nCn
LL c = binomialCoeff(2*n, n);
// return 2nCn/(n+1)
return c/(n+1);
}
int main(){
//std::ios_base::sync_with_stdio(0);cin.tie(0);
//FI;FO;
int t = 0, z = 0, len;
LL n, k = 0, m = 0; //int ans = 0;
rep(l,25)
cat[l] = catalan(l);
bool f = 0;
while(sl(n) != EOF){
FOR(l, 1, 25){
if(cat[l] == n){
cout << l << nl;
break;
}
}
}
return 0;
}