3477 -- System of Linear Equations

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Language:

System of Linear Equations

Time Limit: 2000MS		Memory Limit: 131072K
Total Submissions: 615		Accepted: 85		Special Judge

Description

Solve the system of linear equations

$\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\\vdots\\b_m\end{pmatrix}$

subject to

x_i ≥ 0, ∀i = 1, 2, …, n.

Input

The input in is the following format with 1 ≤ m, n ≤ 100.

m n
a₁₁ a₁₂ … a_1n b₁
a₂₁ a₂₂ … a_2n b₂
… … … … …
a_m₁ a_m2 … a_mn b_m

All numbers except m and n are real numbers.

Output

If any solutions exist, output one of them in the following format.

x₁
x₂
…
x_n

Otherwise declare that the system is inconsistent by printing “impossible”. An special checker program that admits an absolute error of 10⁻¹⁰ is used to verify your results.

Sample Input

2 3
1 1 0 36
-1 1 -1 4

Sample Output

16
20
0

Source

POJ Founder Monthly Contest – 2007.12.30, frkstyc

[Submit] [Go Back] [Status] [Discuss]

Home Page Go Back To top