The problem was created by Clive Fraser - thanks a lot!
A crime has been committed on Logic Island and Inspector Plod has been sent out to solve the crime and arrest the culprit. He has been
forewarned about the strange nature of Logic Island and is feeling rather apprehensive. There are two kinds of inhabitant on the island.
One kind always tells the truth and the other kind always tells lies. In addition to this, the inhabitants don't like associating with people
from the outside world. When they do have any interaction with outsiders they always do so through a series of puzzles. Fortunately there is a
being called the Oracle on Logic Island. The Oracle is not one of the inhabitants of the island but has a good relationship with them.
The Oracle never gives false information so Inspector Plod has been advised to begin by seeking an audience with the Oracle.
After explaining his visit to the Oracle, Inspector Plod was told to wait while the Oracle consulted the inhabitants. On returning, the Oracle
said that the inhabitants will not answer any questions relating to the crime but each of them will provide a short written statement which is
relevant to the crime. The statements given by the Truth tellers, taken together, will provide sufficient information to identify the culprit
and to get a successful prosecution. However, the statements from the Liars will contain false information which is deliberately designed to
confuse the issue. The Oracle also said that the inhabitants would each answer a single question provided that it was unrelated to the crime
and that each inhabitant is asked exactly the same question.
Inspector Plod thought carefully and came up with a question which would identify the Truth tellers. To ensure that his idea would work he worded the question very carefully. This is the question:
What is the total number of inhabitants of Logic Island (excluding the Oracle and myself) who speak the Truth?
With this question all of the Truth tellers will give exactly the same answer, while the Liars will give a variety of different answers.
The inspector was feeling very pleased with himself. The Oracle went off to give the question to the inhabitants and returned with the
following message. The inhabitants will be pleased to answer your question but will do it in their own way. Each inhabitant will reply with two
numbers. If the inhabitant is a Truth teller then the correct answer will be either of the two numbers or any number in between these two
numbers. In other words the inhabitant is specifying a range of numbers. If the inhabitant is a Liar then the required answer will definitely
not be in the specified range. The Oracle then went on to explain that the inhabitants would choose their answers carefully so that there would
be only one way of interpreting them which is consistent with all of the answers. In other words, if Inspector Plod can solve the puzzle he
will uniquely determine for each of the inhabitants whether they are Truth tellers or Liars.
In this problem you will be given the two numbers supplied by each of the inhabitants and must determine, for each inhabitant, whether they
are a Truth teller (T) or a Liar (L).
For the actual problem we will use the Linear Congruential Generator to generate the two
numbers for each inhabitant. A random value X(n) is generated using the formula:
X(n) = (A * X(n-1) + C) % M
In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the
modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first
random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of
the data for the problem.
The example below is made deliberately small, with just 6 inhabitants (N = 6) so that you can use it to test your ideas. The number of
inhabitants in the actual problem will be much larger. For this example, the random seed X(0) is taken to be 0 (it will not be 0 in the
actual problem). We need 12 random values for the 6 pairs of numbers. The first 12 values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237 234863 355586
We will use each number to generate one of the numbers given by an inhabitant. We will do this as follows. We need to generate a number V in
the range 0 .. N inclusive. This is given by V = X(n)%(N+1). In this example N = 6 so the first number is given by 700001 %7 = 1
The numbers given by the 6 inhabitants are: 1, 1, 1, 0, 6, 3, 1, 4, 5, 1, 6, 0.
Re-writing these as ranges gives: [1, 1], [0, 1], [3, 6], [1, 4], [1, 5], [0, 6].
Each of the 6 inhabitants is either a Truth teller or a Liar. There are 64 possible combinations to consider but only one of them is
consistent with all of the information. We can represent this arrangement as a 6 character string of characters T and L. The order of the
characters corresponds to the order in which the inhabitants gave their answers. You should be able to verify that the correct combination is
LLTTTT. Inhabitants 1 and 2 are Liars but inhabitants 3, 4, 5 and 6 are Truth tellers.
Input/Output description: The first and only line of the input data will contain 2 space separated integers. These are the random seed X(0)
and the problem size N (the number of inhabitants).
You need to determine for each inhabitant, whether they are a Truth teller or a Liar.
Give your answer as a single string of N characters (T or L).
Example:
input:
0 6
answer:
LLTTTT