TopCoder problem "TwoEquations" used in SRM 287 (Division I Level One , Division II Level Two)

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".



Parameters:String, String
Method signature:String solve(String first, String second)
(be sure your method is public)


-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.


-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.


"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.
"(-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.
"1*X + 0*Y = 1"
"1*X + 0*Y = 1"
"1*X + 3*Y = 1"
"2*X + 6*Y = (-1)"
"0*X + 0*Y = 0"
"(-3)*X + (-3)*Y = 0"

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Simple Math, String Parsing