7335. Spheres

Problem code: KULE

John has a certain number of spheres. Almost all of them have identical weight apart from one. There are a lot of them and John cannot say which one differs from the other ones by himself. You can help him to determine which sphere it is by using the pair of scales.

Input/Output

In the first line of the input there is one integer n [3 <= n <= 100 000] that stands for the number of spheres which John has. The spheres are numbered from 1 to n.

You can give John two types of orders (just print them to standard output):

• WEIGHT m a1 a2 ... am b1 b2 ... bm

Weighting spheres. All numbers should be separated with a space and they stand for: m - number of spheres that should be put on one of the scales (there should be the same amount of spheres on both of the scales), a1 a2 ... am - identifiers of spheres that you want John to put on the left scale and b1 b2 ... bm - identifiers of spheres that you want John to put on the right scale.

After conducting the weighting John will tell you about the outcome (which you will be able to read from the standard input). Possible answers are LEFT - spheres on the left scale are heavier, RIGHT - spheres on the right answer are heavier, EQUAL - spheres on both scales have equal weight.

After conducting the weighting John is ready right away to execute the next order.

However, you should remember that if the weighting's number is too high John can become quite bored...

• ANSWER k

Answering. This order is to give information that k is the identifier of the searched sphere; however if the sphere we are looking for is lighter than the other ones you should precede that with a '-' sign.

John no longer needs you after that command (your program should end).

Example

```John: 3
You:  WEIGHT 1 1 2
John: LEFT
You:  WEIGHT 1 1 3
John: EQUAL
You:  ANSWER -2
```

Remark: Program should clear the output buffer after printing each line. It can be done using fflush(stdout) command or you can set the proper type of buffering at the beginning of the execution - setlinebuf(stdout).

 Added by: japi Date: 2010-09-19 Time limit: 2s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All

hide comments
2013-06-04 13:02:33 Ujjawal
Getting Wrong Answer for test case 2. Admin please send me the test case via mail. My email id is bhavishya235@gmail.com
2012-08-07 21:33:07 :D
People! Read through comments before asking questions!
2012-08-07 19:33:33 (Tjandra Satria Gunawan)(曾毅昆)
I can't believe... Fast I/O plus O(log(n)) algorithm is TLE? Is there something Wrong???
2012-04-04 15:29:33 Salem Malikic
What is the greatest number (as function of n) of "WEIGHT" requests that we can ask ?
2012-04-04 15:03:33 Nenad
I get TLE on the second test. Does anyone know what is that test like?
2012-02-13 14:58:22 Antonio Carlos
It has to be a good solution, but not necessarily optimal.
At least my algorithm solves the twelve stones problem between 3 and 4 weightings, depending on which stone is counterfeit. It is known that this problem can be solved with 3 weightings at the most.
2011-08-22 04:04:43 Ivan Stošić
I am using an algorithm that uses 3-4 queries more than what i think is optimal. I am getting TLE.
Maybe it's because something's wrong with my reading?

Last edit: 2011-08-27 04:35:39
2011-07-26 19:35:15 cegprakash
will it be accepted if i ask 1 more query than that of optimal number of queries?
2011-07-26 19:35:15 pravinth
will there be one odd sphere always? i mean there wont be any usecase where all spheres are of same weight. ???

Last edit: 2011-01-15 16:16:29
2011-07-26 19:35:15 :D
I just checked on Polish spoj, that the number of queries is limited and the effect of asking to many questions is also TLE! The description should be changed and it should be specified what that limit is. Should it be optimal and what does that mean for this problem?

UPDATE: Finally solved it. The only hint I can give is that the solution must be really sharp. Think hard about the most efficient strategy (mine was quite complex).

Last edit: 2011-01-17 23:23:47
SPOJ © 2013 Sphere Research Labs. All Rights Reserved.