System Solver

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

A system of linear equations is a collection of linear equations involving the same set of variables. A general system of m linear equations with n unknowns can be written as:

\displaystyle \begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2   &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& b_1 \\
a_{21} x_1 &&\; + \;&& a_{22} x_2   &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& b_2 \\
\vdots\;\;\; &&     && \vdots\;\;\; &&                && \vdots\;\;\; &&     &&& \;\vdots \\
a_{m1} x_1 &&\; + \;&& a_{m2} x_2   &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& b_m.
\end{alignat}

Here, x_1, x_2, \dots, x_n are the unknowns, a_{11}, a_{12}, \dots, a_{mn} are the coefficients of the system, and b_1, b_2, \dots, b_m are the constant terms. (Source: Wikipedia)

Write a program that solves a system of linear equations with a maximum of 100 equations and variables.

Input Specification

Line 1 of the input contains integers n and m (1 \le n, m \le 100), indicating the number of variables to solve for and the number of equations in the system.
The next m lines will each contain n+1 integers, where the first n integers are the coefficients of the equation and the last integer is the constant term.
Every number in the input is guaranteed to fit in a 32-bit signed integer.

Output Specification

If the system can be solved, output n lines, the values of the unknowns x_1, x_2, \dots, x_n, accurate within \pm10^{-5}.
If there are no solutions to the system, or if there are infinite solutions to the system, output NO UNIQUE SOLUTION.

Sample Input 1

2 2
1 3 4
2 3 6

Sample Output 1

2
0.66667

Explanation

This asks for the solution(s) for x in the system:

\displaystyle \begin{cases} x + 3y = 4 \\ 2x + 3y = 6 \end{cases}

Solving for x in the first equation gives x = 4 - 3y. Substituting this into the 2-nd equation and simplifying yields 3y = 2.
Solving for y yields y = \frac{2}{3}. Substituting y back into the first equation and solving for x yields x = 2.
Therefore the solution set is the single point (x, y) = (2,\frac{2}{3}).

Sample Input 2

2 3
6 2 2
12 4 8
6 2 4

Sample Output 2

NO UNIQUE SOLUTION

Explanation

All of the lines are parallel. Therefore, the system of equations cannot be solved.


Comments

There are no comments at the moment.