Coins [III]
In this problem you are presenting with evenly weighted coins, except you aren't! Three of the coins are actually heavier than the others (and are equally heavy), and you want to find them efficiently.
You are equipped with a three-sided seesaw, meaning you can put three piles of coins on the 3 sides and observe what piles are heavier than others.
In this interactive problem, determine the weighted coins using the seesaw, making few queries.
Interaction
This is an interactive problem. So rather than reading input once and printing output once, your program should communicate to the judge using input and output.
Interaction will start with a single integer , the number of coins. These coins are labelled 1 through to inclusive.
Queries may then start. Your program can use the seesaw by writing a query of the form
TEST {pile 1} | {pile 2} | {pile 3}
Where pile 1/2/3 are space separated integers. For example, to weigh coins 1 and 3 against coins 2 and 4 against coins 5 and 6, you can do:
TEST 1 3 | 2 4 | 5 6
The judge will then print 1
, 2
and 3
separated by >
to indicate piles are bigger than each other. For example: 1 2 > 3
would mean that while piles 1 and 2 weigh the same, both are heavier than pile 3. Whereas 3 > 1 > 2
means that pile 3 is heavier than pile 1 which is in turn heavier than pile 2.
Once you've determined the weighted coins, you end interaction by printing ANS {coin1} {coin2} {coin3}
. For example ANS 3 6 5
.
Constraints
- The total number of queries should not exceed 27.
Example interaction
[JUDGE]: 8
[PROCESS]: TEST 1 2 | 3 4 | 5
[JUDGE]: 2 > 1 > 3
[PROCESS]: TEST 4 | 3 |
[JUDGE]: 1 > 2 > 3
[PROCESS]: TEST 7 8 | 5 6 | 1 3
[JUDGE]: 2 1 > 3
[PROCESS]: TEST 5 7 | 1 3 | 6 8
[JUDGE]: 3 > 1 2
[PROCESS]: ANS 4 6 8
Comments