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:

a11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2am1x1+am2x2++amnxn=bm.

Here, x1,x2,,xn are the unknowns, a11,a12,,amn are the coefficients of the system, and b1,b2,,bm 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 (1n,m100), 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 106.

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 x1,x2,,xn. Your solution will be considered correct if each value has at most 105 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

Copy
2 2
1 3 4
2 3 6

Sample Output 1

Copy
2
0.66667

Explanation for Sample Output 1

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

{x+3y=42x+3y=6

Solving for x in the first equation gives x=43y. Substituting this into the 2-nd equation and simplifying yields 3y=2.
Solving for y yields y=23. 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,23).

Sample Input 2

Copy
2 3
6 2 2
12 4 8
6 2 4

Sample Output 2

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