11565 - Simple Equations

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

Moderator: Board moderators

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11565 - Simple Equations

Post by Sedefcho » Sun Feb 15, 2009 9:53 pm

I am not sure what it means O(N) and O(N^2)
(in the previous post) because this problem has
three input parameters - A,B,C and no N there
(except the count of the test cases).

Anyway. Here is the correct
output for the input posted above.

INPUT

Code: Select all

29
3 1 3
3 3 3
1 8 21
17 108 121
10 0 100
47 240 1637
18 0 162
23 385 195
37 1664 489
17 0 145
44 544 1224
42 0 1394
24 0 386
12 24 74
8 0 40
55 629 1659
60 1410 2318
34 836 498
46 980 1290
19 56 213
11 48 41
57 3468 1481
52 2210 1350
8 0 130
0 30 38
0 30 38
1 4 9
5 0 13
3 0 5
OUTPUT

Code: Select all

No solution.
No solution.
-2 -1 4
2 6 9
No solution.
1 6 40
No solution.
5 7 11
8 13 16
0 8 9
2 8 34
0 5 37
0 5 19
1 3 8
0 2 6
1 17 37
3 10 47
4 11 19
4 7 35
1 4 14
No solution.
6 17 34
5 13 34
-3 0 11
-3 -2 5
-3 -2 5
No solution.
0 2 3
0 1 2

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11565 - Simple Equations

Post by kbr_iut » Mon Feb 16, 2009 4:27 pm

O(N), O(N^2) ,O(N^3),O(NlogN) these kind of notations are known as complexity of a certain method of algorithm.
generally there are three notations.
===> big Oh
===> big omega
===> big theta
Normally we count this notation by hand seeing at the iteration.....
if u want to know more, then u can see complexity of algorithm topic in any algorithm book.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11565 - Simple Equations

Post by Sedefcho » Mon Feb 16, 2009 9:16 pm

I don't think you got my remark.

Now, I think that by N you meant maybe the number 10,000 in the context
of this problem (or which is basically the same N = max(A,B,C)). I guess this
makes most sense to be denoted as N (in the sense you mentioned it) as
this number is the upper limit for A,B and C.

But if so, I don't know how you can get ACC with
an O(N^2) solution here. Anyway, thanks.

By the way both 11565 and 11571 have O(1) solutions
(for each single test case, I mean).

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11565 - Simple Equations

Post by Obaida » Tue Feb 17, 2009 8:14 am

I used the method of divisor.
That is as B = x*y*z;
so i calculate the divisor of B who can be x. and search for the combination.
But i got stuck in B=0. What can be d solution for that. :oops:
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11565 - Simple Equations

Post by Sedefcho » Tue Feb 17, 2009 2:47 pm

Obaida, are you asking seriously
or is this just a kind of joke ? :)

I guess it is a joke, the problem says
1 <= A,B,C <= 10000.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11565 - Simple Equations

Post by Obaida » Mon Feb 23, 2009 5:47 am

I am sorry i was thinking to make a solution for extreme case. :oops:
try_try_try_try_&&&_try@try.com
This may be the address of success.

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 11565 - Simple Equations

Post by aybek » Mon Feb 09, 2015 6:00 am

Good day!
I think this problem is solvable with careful bruteforce.

We have 3 equations, but there is also another restriction, it is x < y < z.
That is why, test

Code: Select all

1
3 1 3
must be answered:

Code: Select all

No solution.
From the third equation we can make conclusion that, range of variables' values is [-100, 100].
If you have found solution where {x, y, z} is not increasing sequence, then it is guaranteed that there is another solution where x < y < z, coz all operations are associative.

Post Reply

Return to “Volume 115 (11500-11599)”