PROBLEM STATEMENT
You are given two strings, first and second. Each of these strings contains a simple linear
equation with variables x and y. Your task is to determine whether this pair of equations has a
unique solution, and if so, to compute it.
Each of the equations is of the form "A*X + B*Y = C". The spaces must appear exactly as in this
example, i.e., there is exactly one space both before and after the signs "+" and "=", and there
are no other spaces. The coefficients A, B, and C are integers. If a coefficient is non-negative,
the equation contains just the number, without the unary plus sign. If a coefficient is negative,
it is always enclosed in parentheses, and it contains the unary minus sign. No coefficient will
contain unnecessary leading zeroes.
If the pair of equations has a unique solution, return the solution formatted as a string of the
form "X=A/B Y=C/D", where A, B, C, and D are integers such that both fractions A/B and C/D are
reduced, and the numbers B and D are positive. The numbers should be encoded in the same way as
the coefficients of the equations -- i.e., negative numbers must be enclosed in parentheses.
If the pair of equations has more than one solution, return the string "MULTIPLE SOLUTIONS". If
the pair of equations has no solutions,
return the string "NO SOLUTIONS".
DEFINITION
Class:TwoEquations
Method:solve
Parameters:string, string
Returns:string
Method signature:string solve(string first, string second)
NOTES
-A fraction A/B is called reduced if and only if the greatest common divisor of A and B is 1. Note
that each rational number corresponds to exactly one reduced fraction with B>0.
CONSTRAINTS
-first and second will be formatted as described in the problem statement.
-All coefficients in both equations will be integers between -9 and 9, inclusive.
EXAMPLES
0)
"1*X + 2*Y = 6"
"1*X + (-4)*Y = (-3)"
Returns: "X=3/1 Y=3/2"
Multiply the first equation by two, then add the second equation to the first one. You will get a
new equation: 3*X = 9. Thus X=3. If we substitute this into one of the original equations, we get
Y=3/2.
1)
"(-3)*X + 0*Y = 7"
"0*X + 8*Y = 6"
Returns: "X=(-7)/3 Y=3/4"
This time we can compute each of the variables separately. Note that in the result, the numerator
(not the denominator) of X is negative, and that it is enclosed in parentheses. Also, note that
the value of Y is output as a reduced fraction.
2)
"1*X + 0*Y = 1"
"1*X + 0*Y = 1"
Returns: "MULTIPLE SOLUTIONS"
3)
"1*X + 3*Y = 1"
"2*X + 6*Y = (-1)"
Returns: "NO SOLUTIONS"
4)
"0*X + 0*Y = 0"
"(-3)*X + (-3)*Y = 0"
Returns: "MULTIPLE SOLUTIONS"
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.