10784 - Diagonal

[sazzadcsedu]

whats wrong with my code??
plz someone help.
is my code/algo ok?

Code: Select all

          #include<stdio.h>
          #include<math.h>  

         int  main()


      {  
         unsigned  long long x;
         long long n;
         long long a,b,c;  
         int  ncase=1;
         while(scanf("%llu",&x)==1)
         { 
 
           if(x==0)
           break;   

          a=1;
          b=-3;
          c=(-2)*x;
          n=(int)((-b+sqrt(b*b-4*a*c))/2*a);
          n=n+1; 
          printf("Case %d: %lld\n",ncase,n);

	  ncase++;
     
	     }
		 
	return 0;
	} 

[newkid]

i think your solution will fail when x (the input) is 9.
what does your program outputs for that?

[newkid]

my acc program returns 6 for 9 while your one returns 7
hope it helps

[sm_programmer]

Hi everyone!

I did this problem in C, and works well w/test cases, but for some reason it gives me WA!

Code: Select all

Removed after AC

I think I'm not doing the rounding properly, but I tried removing the ceil() of the square, and I still get WA...

Hope someone will find if I'm just doing it wrong. Thanks!

[brianfry713]

Use double instead of float.

[sm_programmer]

Oh, you were right! Just made that change, and got AC!!!

BTW, why is it necessary to use double instead of float, even when I convert the value to unsigned long long?

Is it perhaps for the 15-digit precision it uses for the square root, besides the 7-digit precision of the former?

Thanks, anyway.

[brianfry713]

sqrt and ceil return a double. By casting that to a float you were losing precision.

[sm_programmer]

Oh, yes, you're right.

Thanks, Brian!

[partha31]

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
double N,c=0;
while(cin>>N)
{
if(N==0)
break;
c++;
int n=(3+sqrt(9+8*N))/2;
if(((n*n)-3*n)/2<N)
n=n+1;
cout<<"Case "<<c<<": "<< n<<endl;
}
return 0;
}
what is the problem here???

[lighted]

Problem is that N can be 10^15, so n * n will have overflow of int.
Use long long instead of int.

[ssavi]

Code: Select all

#include<stdio.h>
int main()
{
    long long int n, x=0, i, count, mul;
    while(scanf("%lld",&n)==1 && n>0)
    {
        i=1; mul=-1; count=0;
        while(mul<0)
        {
            mul = (i*i)-(3*i)-(2*n);
            count++;
            i++;
        }
        printf("Case %lld: %lld\n",++x,count);
    }
    return 0;
}

Why I am getting TLE & WA.

[lighted]

You can solve your quadratic equation in O(1).

[Zyaad Jaunnoo]

Solved by binary search.