11042 - Complex, difficult and complicated

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

Moderator: Board moderators

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

11042 - Complex, difficult and complicated

Post by temper_3243 » Sun Jun 04, 2006 6:40 pm

hi,
Does anyone have testcases for the problem 11042. When i submit the code, the problem says received but nothing about status.


Can someone post good test cases.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Mon Jun 05, 2006 12:44 am

HI,
I am getting WA. Can some one tell me where i am doiing things wrong .

Code: Select all

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

# define M_PI		3.14159265358979323846	/* pi */

double sqrt(double );
double atan(double );
double fabs(double );

int main()
{
       int i,a,b,no,k;
       double  m,n,z;

       scanf(" %d",&no);
       while(no--)
       {
               scanf(" %d %d",&a,&b);

               z=sqrt(a*a + b*b);

               if(a==0)
                       m=M_PI/2;
               else
                       m=atan((double)b/(double)a);

               if(m==0)
               {
                       printf("1\n");
                       continue;
               }

               k=fabs(M_PI/m);

               if (fabs(fabs(k*m ) - M_PI) < 0.00009)
		{
			if(pow(z,k) <= pow(2,30))
                       printf("%d\n",k);
		else
                       printf("TOO COMPLICATED\n");
		}
               else
                       printf("TOO COMPLICATED\n");
       }
       return 0;
}




mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jun 05, 2006 2:37 am

Here are some inputs for which your program gave wrong answer (at least, on my computer):

Code: Select all

5
0 0
-153 -265
-153 265
-97 -168
97 168
Correct answer for the first case is 1, for the rest -- "TOO COMPLICATED".

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

Post by fernando » Mon Jun 05, 2006 3:45 am

What's the approach or mathematical concept required to solve this problem?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jun 05, 2006 6:27 am

This is the top Google link:
http://www.clarku.edu/~djoyce/complex/

The program above uses "polar coordinates", I solved it using cartesian coordinates ("complex plane"). (check the corresponding parts in that tutorial)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jun 05, 2006 4:51 pm

I used brute force and got Accepted in 0.000 seconds.
Ami ekhono shopno dekhi...
HomePage

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jun 06, 2006 8:25 am

Jan wrote:I used brute force and got Accepted in 0.000 seconds.
Is the solution simply to loop over N and stop when the number becomes real. If so, when should the looping stop if there is no solution.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Jun 06, 2006 8:49 am

shamim wrote:
Jan wrote:I used brute force and got Accepted in 0.000 seconds.
Is the solution simply to loop over N and stop when the number becomes real. If so, when should the looping stop if there is no solution.
Not exactly , you nead a condition to stop the loop ( for the case that the result is TOO COMPLICATED ) but the rest is completely brute force
hope it helps

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jun 06, 2006 8:49 am

I picked n=1000 and it worked. One could probably come up with a case that breaks it. (hm, maybe not - a,b are integers and they'll end up being > 2^30 really fast... silly me.. why did I pick such a high number?)

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jun 06, 2006 3:03 pm

Darko wrote:I picked n=1000 and it worked. One could probably come up with a case that breaks it. (hm, maybe not - a,b are integers and they'll end up being > 2^30 really fast... silly me.. why did I pick such a high number?)

I choose 100 and got AC.

Is it always true, as n increases the abs(real) part will also increase. Since i*i is -1, shouldn't at times, the real part decrease or something.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jun 06, 2006 3:33 pm

Spoiler

My method is -

Code: Select all

Suppose a and b given...
I considered x=1 and y=0

1. I have two complex numbers -

P = x + iy
Q = a + ib

2. Every time multiply P and Q and update x, y (x, y to srore the multiplication results. x contains real part and y contains complex part) .

3. If abs (x) > 2^30 then TOO COMPLICATED. End.

4. If y = 0, Got the Solution. End.

5. Goto step 1.
Ami ekhono shopno dekhi...
HomePage

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Jun 06, 2006 5:40 pm

When you convert the number to polar form ... then

SPOILER
(a+ib)^n
= r^n (cos (n.t) + i sin (n.t) )

You can safely say that if r^n is greater than 2^30 then TOO COMPLICATED
Where's the "Any" key?

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Fri Jun 09, 2006 5:25 am

Hi guys,

Spoiler

I think there can not be any input which output is greater than 4.
There is only 4 Possible output for the problem
1. 1
2. 2
3. 4
4. TOO COMPLICATED

Try to categorize all the input into 4 partition and you can solve it using only few If-else.

No need to use any loop
No need to use any cos or sin function

Sorry for my poor english

Take care
Practice Makes a man perfect

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Jun 11, 2006 2:23 am

mrahman wrote:Try to categorize all the input into 4 partition and you can solve it using only few If-else.

No need to use any loop
No need to use any cos or sin function
You are absolutelly right... After experiencing a few numbers by hand one can easily find those categories.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Fri Sep 22, 2006 5:30 pm

I think there can not be any input which output is greater than 4.
There is only 4 Possible output for the problem
1. 1
2. 2
3. 4
4. TOO COMPLICATED
I don't think so... for the input:

1
96 32

the output is

12
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Post Reply

Return to “Volume 110 (11000-11099)”