ROBOWORLD - Robot World

Garima is a student of Artificial Intelligence, she is specializing in robotics. She is designing various simulations to test run her robot algorithms. The robot works in a 1-dimensional world (which has a starting point known as origin). If a robot is 5 units away from origin, then robot is said to be at the ordinate 5. Similarly if robot is 2.5 unit away from origin, then robot is said to be at the ordinate 2.5. Robots usually operate in groups. A group of robots can be described in terms of their individual ordinates. For example, if there are three robots in a group which are present at 1.3 units, 0 units and 5 units respectively away from origin, then we can say that the robot group is the ordered tuple <1.3, 0, 5>.

One of the attributes of the robot is its power. Given a robot's ordinate we can determine the power of a robot using a given linear function called robot power function. Even though linear functions are of the form ax + b, but robot power functions are of the form ax and don't have any constant term. Robot's in the same group have same robot power function. For example, if robot power function is given by function f(x) = 2x, then robots in the group <1.3, 0, 5> have powers 2.6 units, 0 units and 10 units respectively. The average power of the group is given by (2.6 + 0 + 10)/3 = 4.2.

Given two robot groups (containing same number of robots), Garima wants to find robot power functions f(x) and g(x) such that f(x) = ax and g(x) = bx and 'a' and 'b' are positive integers and absolute difference between the average power of the two robot groups is minimized. Since 'a' and 'b' needs to be small, so a2 + b2 should also be minimized.

More mathematically, given the robot groups <x1, x2 ... xn> and <y1, y2 ... yn>, find positive integers 'a' and 'b' such that |(1/n) * ∑ (a*xi - b*yi)| is minimized. Since, there is a possibility that there are multiple such 'a' and 'b' so Garima puts yet another constraint of minimizing a2 + b2

Input

The first line tells the number of test cases 't'.

Each test case begins with a number 'n'. 'n' corresponds to the number of robots in robot groups.

The next 'n' lines of the test case consist of two space separate real numbers. For example the ith line contains real numbers 'xi' and 'yi' which represent the ordinates of one robot from each of the two robot groups.

These 'n' lines describe the two robot groups <x1, x2 ... xn> and <y1, y2 ... yn>. It is also given that not all robots in any robot group are 0 units away from origin.

1 ≤ t ≤ 100

1 ≤ n ≤ 1000

0 < ∑xi ≤ 1014

0 < ∑yi ≤ 1014

xi and yi can have at most 4 digits after decimal.

Not all of xi are zero and not all of yi are zero.

All xi ≥ 0 and all yi ≥ 0

#Note: xi and yi are real numbers and NOT necessarily floating-point numbers

You can read more about floating-point numbers here: https://en.wikipedia.org/wiki/Double-precision_floating-point_format

Output

Single line per test case.

Each line is of the form:

f(x) = ax, g(x) = bx

where 'a' and 'b' are the respective positive integers satisfying all the constraints given in the problem.

#Note: The uniqueness of 'a' and 'b' is mathematically guaranteed.

Example

Input:
3
4
7.4 0.0027
0.022 72
0.002 0.000
0.0 0
4
8.6 0.004
0.006 0.092
0.5 0
0.002 0.004
4
25 0.73
0.0062 1.4
1 0.012
0.07 0.0000

Output:
f(x) = 720027x, g(x) = 74240x
f(x) = 25x, g(x) = 2277x
f(x) = 10710x, g(x) = 130381x

Explanation

For the first test case, we can observe that |(720027 * 7.4 - 74240 * 0.0027) + (720027 * 0.022 - 74240 * 72) + (720027 * 0.002 - 74240 * 0.000) + (720027 * 0.0 - 74240 * 0)| = 0.

Since minimum absolute value can be zero so 720027 and 74240 satisfies the minimization constraint. Also, 720027 and 74240 are the smallest such values, hence they satisfy the minimization of a2+b2 constraint too.


Added by:Amitayush Thakur
Date:2021-02-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own

hide comments
2021-02-21 22:16:45
I've verified that the test data are correctly formatted and that the constraints hold, but I still get WA with no idea where the error might be (other than the logic that is). I feel psetter is enacting revenge on everyone for his time on SHP ;)

Edit: Giving up after 2h of having nowhere to look for a mistake. Congrats to BlueMary for finding the dirty trick probably hidden somewhere in the convoluted statement, perhaps I'm not smart enough for this, but I just don't trust psetter enough to waste any more time on this. Be warned.

BTW. If xi >= 0 and not all xi are zero (which holds according to my tests), then constraint for sum(xi) should be stated as strictly greater than 0.

[Amitayush] I couldn't resist giving a hint because you tried so hard. There is no dirty trick (you can trust me on that). [--Removed the hint--] . I also updated the constraints as you mentioned.

[NG]: I'm not operating on floats. I have no idea what you're talking about. I certainly hope the judge is not expecting results with precision errors stemming from float use..

[Amitayush]: [--Removed the hint--] I would also recommend reading https://docs.python.org/3/tutorial/floatingpoint.html and IEEE-754 “double precision” (https://en.wikipedia.org/wiki/Double-precision_floating-point_format)

[NG]: Like I said, I was not operating on floats because of all well known issues they introduce. I did not even try any defensive input methods, assuming the data follow CP convention with values that actually fit the container. Again, a dirty trick, and the convoluted statement with typos unfortunately encourages assumptions. Without the nasty values in sample cases, the problem is almost unsolvable.

[Amitayush]: Now that you have solved it, I am removing the hints. Regarding typos, I don't think typos changed any of the technical details about the problem or affected its constraints. I don't usually check my problem statement for grammatical correctness, so there can be some punctuation errors/spelling mistakes. I hope you forgive me for that given English is not my native language :) . I disagree that the problem statement is convoluted. A problem statement being convoluted is a subjective issue, what seems convoluted to you might seem simple to someone else. The constraints mentioned in the problem actually hints towards the defensive input strategy. I would say it is quite conspicuous from the constraints xi <= 10^14, "at most 4 digits after the decimal", and "xi is real number" (and not floating-point number) that something is different about the problem. Finally, I would like to point out that if the problem statement was so unconventional how could BlueMary solve it in one go without any hints. However, I would agree that certain aspects of the problem could reflect idiosyncrasies of the problem setter. I would also like to mention that a good thing about being a problem-setter is one gets to read other's code, I have read your solutions and I like the way you write comments at the beginning of all your programs :) . I do take some of your feedback on problem design. Thank you for solving :)

Last edit: 2021-02-22 19:28:33
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.