Page 2 of 2
Re: 10784 - Diagonals
Posted: Sun Dec 28, 2008 11:22 pm
by 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;
}
Re: 10784 - Diagonals
Posted: Mon Dec 29, 2008 3:40 am
by newkid
i think your solution will fail when x (the input) is 9.
what does your program outputs for that?
Re: 10784 - Diagonals
Posted: Mon Dec 29, 2008 3:43 am
by newkid
my acc program returns 6 for 9 while your one returns 7
hope it helps
Re: 10784 - Diagonals
Posted: Sun Jun 30, 2013 9:53 am
by sm_programmer
Hi everyone!
I did this problem in C, and works well w/test cases, but for some reason it gives me WA!
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!
Re: 10784 - Diagonals
Posted: Tue Jul 02, 2013 1:09 am
by brianfry713
Use double instead of float.
Re: 10784 - Diagonals
Posted: Tue Jul 02, 2013 1:44 am
by 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.
Re: 10784 - Diagonals
Posted: Tue Jul 02, 2013 10:42 pm
by brianfry713
sqrt and ceil return a double. By casting that to a float you were losing precision.
Re: 10784 - Diagonals
Posted: Wed Jul 03, 2013 12:12 am
by sm_programmer
Oh, yes, you're right.
Thanks, Brian!
Re: 10784 - Diagonals
Posted: Fri Aug 15, 2014 12:07 am
by 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???
Re: 10784 - Diagonals
Posted: Fri Aug 15, 2014 3:57 am
by lighted
Problem is that N can be 10^15, so n * n will have overflow of int.
Use long long instead of int.
Re: 10784 - Diagonal
Posted: Wed Nov 26, 2014 10:16 pm
by 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.
Re: 10784 - Diagonal
Posted: Thu Nov 27, 2014 4:01 pm
by lighted
You can solve your quadratic equation in O(1).
Re: 10784 - Diagonal
Posted: Wed Jan 07, 2015 8:42 pm
by Zyaad Jaunnoo
Solved by binary search.