System Solver

View as PDF

Submit solution

Points: 15
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 have absolute value at most 10^6.

It is guaranteed that the input is generated randomly. Specifically, for each test case, n and m will be picked arbitrarily, and so will two other integers, l and r. Then, all other values in the input will be integers picked uniformly at random between l and r.

Output Specification

If the system can be solved, output n lines, the values of the unknowns x_1, x_2, \dots, x_n. Your solution will be considered correct if each value has at most 10^{-5} absolute or relative error. 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 for Sample Output 1

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 for Sample Output 2

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


Comments


  • 0
    BalintR  commented on July 4, 2022, 3:47 p.m.

    Added the guarantee that the input will be random since the problem would be much harder than intended otherwise. Also updated the data to meet the new constraints and rejudged all submissions.