Connection Status:
Competition Arena > TwoEquations

TwoEquations

SRM 287 · 2006-02-04 · by misof

SRM 287 · 2006-02-04 · by misof · Brute Force, Simple Math, String Parsing
Class Name: TwoEquations
Return Type: String
Method Name: solve
Arg Types: (string, string)
Problem Statement

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

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"

Submissions are judged against all 141 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoEquations with a public method string solve(string first, string second) · 141 test cases · 2 s / 256 MB per case

Submitting as anonymous