11565 - Simple Equations

[Sedefcho]

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

[kbr_iut]

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.

[Sedefcho]

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]

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.

[Sedefcho]

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]

I am sorry i was thinking to make a solution for extreme case.

[aybek]

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.