10784 - Diagonal

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10784 - Diagonals

Post by sazzadcsedu » Sun Dec 28, 2008 11:22 pm

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
For Hints: http://salimsazzad.wordpress.com

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

Re: 10784 - Diagonals

Post by newkid » Mon Dec 29, 2008 3:40 am

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

Post by newkid » Mon Dec 29, 2008 3:43 am

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

Post by sm_programmer » Sun Jun 30, 2013 9:53 am

Hi everyone! :)

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

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! :D
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

Post by brianfry713 » Tue Jul 02, 2013 1:09 am

Use double instead of float.
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

Post by sm_programmer » Tue Jul 02, 2013 1:44 am

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

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

Post by brianfry713 » Tue Jul 02, 2013 10:42 pm

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

Post by sm_programmer » Wed Jul 03, 2013 12:12 am

Oh, yes, you're right.

Thanks, Brian! :D

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

Re: 10784 - Diagonals

Post by partha31 » Fri Aug 15, 2014 12:07 am

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

Re: 10784 - Diagonals

Post by lighted » Fri Aug 15, 2014 3:57 am

Problem is that N can be 10^15, so n * n will have overflow of int.
Use long long instead of int. :D
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

Post by ssavi » Wed Nov 26, 2014 10:16 pm

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

Re: 10784 - Diagonal

Post by lighted » Thu Nov 27, 2014 4:01 pm

You can solve your quadratic equation in O(1). :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 10784 - Diagonal

Post by Zyaad Jaunnoo » Wed Jan 07, 2015 8:42 pm

Solved by binary search.

Post Reply

Return to “Volume 107 (10700-10799)”