10784

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)! ).

#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;
}