PROBLEM STATEMENT
Sometimes a set of statements can seem paradoxical. For example, the statement
"This statement is false" is paradoxical because if the statement is true, then
it must be false, but if the statement is false it must be true. Similarly,
the set of statements
0. 1 is false
1. 0 is true
is paradoxical. If statement 0 is true, then 1 must be false, so 0 must be
false. On the other hand, if statement 0 is false, then 1 must be true, so 0
must be true.
More precisely, a set of statements is paradoxical if there is no way to assign
a value of "true" or "false" to each statement such that every statement is
true if and only if it is assigned the value "true." Such a set of truth
assignments is called "consistent."
Write a method to determine whether or not a set of statements is paradoxical.
If the set of statements is paradoxical, return "PARADOX". Otherwise, return a
consistent set of truth assignments. If more than one set of consistent truth
assignments exists, return the one that comes first lexicographically, with
"false" coming before "true".
DEFINITION
Class: Paradox
Method Name: solve
Parameters: String[]
Returns: String
Method signature (be sure your method is public): String solve(String[]
statements);
Each statement will be of the form "<num> is <value>" (quotes are for
clarification only), where <num> is a valid statement number and <value> is
either "true" or "false". There will be exactly one space between successive
tokens.
The return value should be either "PARADOX" (quotes should not be in the actual
return String) or a String of the form "<value1> <value2> ... <valuek>" (quotes
are for clarification only), where k is the number of elements in the String[].
Each <valuei> should be either "true" or "false", and there should be exactly
one space between consecutive values.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
* statements contains between 1 and 8 elements, inclusive
* Each element of statements is of the form described above
EXAMPLES
if statements = { "1 is false",
"0 is true" }, then return "PARADOX".
if statements = { "0 is true",
"1 is true" }, then all four possible truth assignments are
consistent. In lexicographical order, the consistent truth assignments are
"false false", "false true", "true false", "true true". So the return value is
"false false".
if statements = { "1 is false",
"3 is true",
"3 is false",
"2 is false",
"0 is true" }, then return "false true false true false".
if statements = { "2 is false" ,
"3 is false" ,
"0 is false" ,
"1 is false" }, then return "false false true true".
if statements = { "5 is false" ,
"7 is true" ,
"1 is false" ,
"0 is false" ,
"3 is true" ,
"2 is true" ,
"4 is false" ,
"6 is false" }, then return "PARADOX".