A few things figuring out helped to solve this problem.
- for n+2 gon there are maximum n*(n+1)/2 -1 (summation of n natural numbers -1 = S) diagonals and minimum S-(n-1) diagonals, that means for S-(n-1) number of diagonals we need minimum n+2 polygon.
- Example : there is no diagonal for triangle , 2 diagonals for Quadrilaterals 5 for pentagons. max number of diagonal can be found simply by subtracting edge number from C(n,r) = n! / ( r! (n – r)! ).
|
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 |
#include <iostream> #include <cstdio> #define ll long long using namespace std; int main() { ll lo,hi,mid; double num,v1,v2,v3; int kase=1; while(cin>>num) { if(num==0) break; lo=0;hi=45000000;mid=(hi+lo)/2;//45000000 bool f=1; while(f) { double m = mid*1.0; v2=m*(m+1)/2-1; if(v2>=num) { if(num>=v2-(m-1)) { printf("Case %d: %0.lf\n",kase++,m+2); f=0; } hi=mid; mid=(hi+lo)/2; } else { lo=mid+1; mid=(hi+lo)/2; } } } return 0; } |