## 10784 - Diagonal

Moderator: Board moderators

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10784 - Diagonals

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;
}
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10784 - Diagonals

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

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10784 - Diagonals

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

sm_programmer
New poster
Posts: 10
Joined: Mon Jun 24, 2013 7:39 am

### Re: 10784 - Diagonals

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!
Last edited by sm_programmer on Tue Jul 02, 2013 1:45 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10784 - Diagonals

Check input and AC output for thousands of problems on uDebug!

sm_programmer
New poster
Posts: 10
Joined: Mon Jun 24, 2013 7:39 am

### Re: 10784 - Diagonals

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10784 - Diagonals

sqrt and ceil return a double. By casting that to a float you were losing precision.
Check input and AC output for thousands of problems on uDebug!

sm_programmer
New poster
Posts: 10
Joined: Mon Jun 24, 2013 7:39 am

### Re: 10784 - Diagonals

Oh, yes, you're right.

Thanks, Brian!

partha31
New poster
Posts: 2
Joined: Tue Jun 10, 2014 11:09 pm

### Re: 10784 - Diagonals

#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
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10784 - Diagonals

Problem is that N can be 10^15, so n * n will have overflow of int.
Use long long instead of int.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

### Re: 10784 - Diagonal

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.
I know I am a Failure Guy .

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek