LinearSolver | Topcoder Archive

Problem Statement

You will be given a list of equations using 2 variables: x and y. An equation like 3x+4y=8 will be denoted by the string (quotes for clarity): "3x+4y=8". More formally, you will be given equations of the form ax+by=c denoted as (quotes for clarity) "ax+by=c", where a,b and c are non-negative integers. You will return all valid solutions, where x and y are integers between 0 and 50 inclusive. A valid solution is a single assignment of values to x and y, such that all of the given equations are satisfied simultaneously.

The returned value will be a list of valid solutions, each of which is formatted (quotes for clarity) "x y", where x and y have no extra leading zeros, and are separated by a single space. The returned values should be sorted in ascending order by x value. If solutions share the same x value, sort them into ascending order by y value. There should be no repeated values in the solution.

Definition

Class:: LinearSolver
Method:: solve
Parameters:: String[]
Returns:: String[]
Method signature:: String[] solve(String[] equations)
(be sure your method is public)

Constraints

equations will contain between 1 and 50 elements inclusive
Each element of equations will contain between 7 and 16 characters inclusive
Each element of equations will have no whitespace
Each element of equations will be formatted "ax+by=c" wherea, b and c are integers between 0 and 1000 inclusivea, b and c have no extra leading zerosAt least one of a, b, and c will be positive

Examples

```
{"1x+1y=1"}
```
```
Returns: { "0 1", "1 0" }
```

{"3x+0y=9",
 "0x+3y=9",
 "1x+1y=6"}

Returns: { "3 3" }

{"1x+1y=6",
 "2x+2y=12",
 "3x+3y=18",
 "1x+2y=7"}

Returns: { "5 1" }

{"1x+1y=6",
 "2x+2y=12",
 "3x+3y=18"}

Returns: { "0 6", "1 5", "2 4", "3 3", "4 2", "5 1", "6 0" }

```
{"251x+0y=1000"}
```
```
Returns: { }
```
```
{"1x+1y=101"}
```
```
Returns: { }
```

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)2024, Topcoder, Inc. All rights reserved.