PROBLEM STATEMENT
There is a famous math problem about 12 coins. You have 12 coins and exactly
one of them is fake, which means that it is either heavier or lighter than real
coins. You do not know whether it is heavier or lighter. You also have a
balance scale. You need to find which coin is fake and whether it is heavier or
lighter in three weighings.
Your task is, given the weighing results, return the practical knowledge you
gain about the coins.
In more detail:
The coins are numbered 1 through 12 inclusive. Each weighing result gives you
the indices of the coins which are put on the left cup of the balance scale,
then the result of the weighing (<, >, =) and the indices of the coins which
are put on the right cup of the balance scale. All items are delimited by
spaces. For example, "1 2 < 3 4" means that you had the coins numbered 1 and 2
in the left cup, the coins numbered 3 and 4 in the right cup, and that the left
cup weighed less than the right cup. Each element of the input String[]
represents one weighing. Given all the results you may conclude that the inputs
are contradictory (They may contradict each other or the assumption that we
have exactly one fake coin). In this case, you should return the String
"CONTRADICTION". If the input is not contradictory you can make some
conclusions about each of the coins. Your conclusions about individual coins
should be of the following types:
- 1) fake and not clear if it is lighter or heavier than real coins,
- 2) fake and lighter,
- 3) fake and heavier,
- 4) real,
- 5) unknown, i.e. no practical knowledge (for all other cases).
You return a String of characters, where each character represents the
conclusion about each coin in the same order as the coins are numbered. The
correspondence between the types of conclusions and the characters is the
following:
- fake and not clear if it is lighter or heavier than real coins - 'F'
- fake and lighter - 'L'
- fake and heavier - 'H'
- real - 'R'
- unknown - 'U'.
NOTES
- Assume that we have exactly one fake coin.
DEFINITION
Class: FakeCoin
Method: result
Parameters: String[]
Returns: String
Method signature (be sure your method is public): String result(String[]
weighings);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- weighings contains between 0 and 10 elements inclusive
- each element of weighings contains no leading/trailing whitespace
- each character of each element of weighings is a digit, a space or a
comparison sign, which is one of '<', '>' or '='. Moreover, each element of
weighings has exactly one comparison sign
- each element of weighings doesn't have two spaces in a row
Each element of weighings has numbers representing coins on the left cup, one
of the characters '<', '>' or '=' representing the result of the weighing, and
numbers representing coins on the right cup:
- coins are numbered from 1 to 12 inclusive
- coin numbers will not have leading zeros
- a coin number will not appear twice in the same weighing
- each cup has between 1 and 6 coins inclusive
- the left cup has the same number of coins as the right cup
As a consequence each element of weighings will contain between 5 and 28
characters, inclusive.
EXAMPLES
1. weighings = {"1 2 3 4 5 6 = 7 8 9 10 11 12"} contradicts the assumption that
exactly one of the coins is fake, return "CONTRADICTION"
2. weighings = {"1 < 2"} means that either the first coin is fake and lighter
or that the second coin is fake and heavier, return "UURRRRRRRRRR"
3. weighings = {"1 2 3 4 = 5 6 7 8", "1 2 3 < 9 10 11", "9 < 10"}, the first
weighing means that the first 8 coins are real, the second weighing tells us
that the fake coin is among the 9th, 10th and 11th coins and it is heavier, the
last weighing tells us that the fake coin is coin number 10 and it is heavier,
return "RRRRRRRRRHRR"
4. weighings = {"1 < 2", "2 < 3"}, return "CONTRADICTION"
5. weighings = {"1 < 2", "2 = 3"}, return "LRRRRRRRRRRR"