[email protected] #5 (Binary) Search

Robotopia

Photo by
DJ Shin

In the wonderful land of Robotopia, life is better than ever. This is thanks to all the robots, who work hard together. Different types of robots come in different forms, that is, different numbers of arms and different numbers of legs. By day, when they are working, robots are grouped so they can be assigned to different tasks. But by night, it is your job to count how many robots there are of each type within each group. Robots are naughty and energetic; they don’t like to stand still and it is difficult to count them. After many exhausting attempts, you are finally able to count how many arms and how many legs there are in total.

We know each group consists of exactly two different types of robots, with at least one of each type in each group. We also know the number of arms and legs that each type of robot has. Can you find out how many robots of each type there are within each group?

The first line contains an integer $n$ $( 1 \leq n \leq 100)$. The following $n$ lines each contain one test case. Each has six integers: $l_1~ a_1~ l_2~ a_2~ l_ t~ a_ t$, where $l_1$ and $a_1$ are the number of legs and arms (respectively) for the first type of robot, $l_2$ and $a_2$ are those for the second type, and $l_ t$ and $a_ t$ are the total number of observed legs and arms. All values are in the range $[1, 10\, 000]$.

For each test case output two positive integers denoting the
number of each of the two types of robots. Give first the count
for the first type listed. If the test case has no solution or
multiple solutions, output “`?`” (a question mark).

Sample Input 1 | Sample Output 1 |
---|---|

3 2 1 4 1 16 5 3 2 5 1 9 4 1 2 3 6 8 16 |
2 3 ? ? |