|
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 |
#include <iostream> #include <cstdio> #define ll long long using namespace std; ll catalan[25]; ll findcatalan(int n) { ll res = 1; int lim; for(int i=n+2;i<=2*n;i++) { if(i%2==0) res*=2; else res*=i; } if((n+2)%2==0) lim = (n+2)/2; else lim = (n+3)/2; for(int i=2;i<lim;i++) { res/=i; } return res; } int binSearch(ll num) { int lw=0,hi=17; int mid; /*while(lw<hi) { mid=lw+(hi-lw)/2; if(catalan[mid]<num) lw = mid+1; else if(catalan[mid]==num) return mid; else if(catalan[mid]>num) hi = mid; }*/ for(int i=1;i<20;i++) { if(num==catalan[i]) return i; } return 0; } int main() { catalan[0]=1; catalan[1]=1; catalan[2]=2; ll num; int idx; for(int i=3;i<20;i++) { catalan[i] = findcatalan(i); } while(cin>>num) { idx = binSearch(num); cout<<idx<<"\n"; } return 0; } |