Last year the IPSC was so successful that we earned n coins. And they are no ordinary coins: they are perfectly identical coins made of solid gold.
Sadly, there are some problems with our coins. First of all, we don’t actually have them. The coins are locked in a vault in Absurdistan. And second, we just got word that one of our coins has been stolen and replaced by a fake one. The fake coin slightly differs from the real ones in weight, but we do not know whether it is heavier or lighter.
So far, our situation looks like one of those weighing puzzles, doesn’t it? We bet you would love to take balance scales and start comparing the weights of some coins in order to identify the fake one as quickly as possible.
Well, it kind of does look like a weighing puzzle, but the weighing part is not the major issue here. Remember that all our coins are in a country far far away? We will not be the ones weighing the coins, we can only send our request to the natives.
Why does this change anything, you ask? Well, for a start, there is no Internet in Absurdistan. Each time we want to make some weighings, we write down a list of requests, send it by regular post and wait a week or so for the answers.
To add insult to injury, the natives in Absurdistan are very lazy. Each time a native is asked to weigh some coins, with probability p = 0.7 he will ignore the request and just give you a random answer instead. That is, only 30% of your requests will actually be executed, the other 70% will receive random answers. On the other hand, the natives are precise. If the native decides to perform the requested weighing, he will always get and report the correct result.
The scales used by the natives are extremely precise balance scales. They consist of two pans (we will call them “left” and “right”) that are connected by a beam with a fulcrum in the middle. One may place some coins into the left pan, some other coins into the right pan, and then read off one of three possible results: either one of the pans is heavier, or the scales balance. (It only makes sense to place the same number of coins onto each pan. If you ask to place more coins into one pan than the other, the pan with more coins will always be heavier. Of course, even if this is the case, the native may still skip the weighing and report a random answer.)
Problem specification
There are n coins, labeled 1 through n. The labeling was chosen uniformly at random. Out of the coins, n − 1 are real and one coin is fake. The fake coin is either lighter or heavier than the real coins. As the counterfeiter was trying his best, both options are equally likely (probability 50%).
You will interact with our grader using multiple submissions. Each submission represents one letter sent to Absurdistan. You will first send some letters that require the natives to perform some weighings, and finally one letter announcing which coin is the fake one and also whether it is heavier or lighter than the real ones. In each letter in which you request weighings, you must request exactly k of them.
In each subproblem of this task there are two criteria you need to satisfy in order to solve the subproblem:
Your answer will only be accepted if you can be at least 99% certain that your answer is correct, based on the weighings you made, their outcomes you received, and the assumption that all random events were independent and had the stated probabilities.
If you fail (by guessing incorrectly, guessing without 99% certainty, or using up all s submissions without guessing at all), the whole subproblem is restarted and you can try again from the beginning. A new fake coin in chosen, and you get to make another s submissions in the “new game”.
Constraints
In both subproblems, the probability of a particular native being lazy is p = 0.7. (That’s a lot!)
Easy subproblem F1: The number of coins is n = 81. You may send at most s = 6 submissions (per restart), and in each submission that requests weighings, you have to request exactly k = 50 of them.
Hard subproblem F2: The number of coins is n = 250. You may send at most s = 11 submissions (per restart), and in each submission that requests weighings, you have to request exactly k = 15 of them.
A different rule replaces the standard limit of at most 10 submissions per subproblem. Here, only Wrong answers count towards the limit. In each subproblem, you may only receive a Wrong answer message at most 9 times. If you receive a 10th Wrong answer, all further submissions will be rejected.
Submission specification
The first line of your file should contain a single letter: either ‘G’ (a guess) or ‘W’ (a list of k weighing requests).
If your submission is a guess, the second line of your submission should contain the number of the fake coin (between 1 and n, inclusive), a space, and a letter. The letter should be ‘L’ if the fake coin is lighter than the real ones, and it should be ‘H’ if the fake coin is heavier.
If your submission is a list of k weighing requests, it should contain exactly k more lines. Each of those lines should contain a string of n characters that describes one weighing request. The i-th character of a request should be ‘L’ if coin i should be placed on the left pan of the scales, ‘R’ for the right pan, and ‘-’ if the i-th coin should remain off the scales.
Evaluation result specification
If your submission is syntactically incorrect, you will receive a Wrong answer with an explanation. A syntax error does not cause a restart, nor is it counted in the s allowed submissions.
If your submission is a successful guess, you will receive an OK, thus solving the subproblem. If your guess fails, you will receive a Wrong answer with an explanation, and the game is restarted.
If your submission is a list of weighing requests, you will receive a Continue and a string of k characters. The i-th character is the result of your i-th weighing request: ‘L’ if the native claims the left pan is heavier, ‘R’ if he claims the right pan is heavier, and ‘=’ if he claims both pans are exactly equally heavy.
Note that each request on your list is handled by a different native, and (independently of each other) each of those natives generates his reply uniformly at random with probability p.
Continue messages do not affect the team’s rank. They are not worth any points, nor do they add penalty time. Wrong answers are scored as usual.
Good advice
If at first you don’t succeed, try again!
As there are probabilities involved, even the best strategy might sometimes fail. If you trust that your game strategy makes sense, give it another attempt if the first one doesn’t make it.
(Of course, if your strategy is bad, your chance to solve this problem would be zero even if we granted you a thousand attempts.)
Example
In the example below, we have n = 6 coins and we request k = 3 weighings at a time.
One possible first submission:
This is what you may receive as our response:
This means that you got the following responses:
If we trusted these answers, we could now conclude that coin 2 is the fake one, and it is heavier than the real coins. (Coins 3, 4, 5, 6 have to be real from the third answer, and then coin 2 is fake and heavier from the second answer.) We could then submit the corresponding guess:
However, in this problem we have to be certain enough before making our guess.
And right now we shouldn’t be too certain yet. After all, each of those three responses has probability 70% of being the result of a random choice. The submission would be evaluated as a Wrong answer, and the subproblem would be restarted.
At the moment (assuming p = 0.7) the actual probability that “2 H” is the correct answer is only about 36.96%. The second most likely answer is currently “1 H” with probability about 16.17%. (The answer “1 H” corresponds, among other possibilities, to the situation when the response to -L---R was generated at random and the other two are correct.)