TopCoder

User's AC Ratio

61.1% (11/18)

Submission's AC Ratio

12.2% (29/238)

Description

在偏遠的競程地區中,有一個神秘人物叫做bb。沒有人知道「bb」這個名子的由來是甚麼,或者它代表甚麼意思,只知道它也許來自於某個古老的傳說。

出身於獨特背景的bb,受到上一代宗師的教導,他的實力是許多人難以想像的。據某些消息來源表示,bb可能是唯一一個在成為國手時還不會解二元一次聯立方程式的人物。然而,經過了短短的幾個月,現在輪到bb要考驗大家會不會解$N$元一次方程組了!

所謂的$N$元一次方程組,長得像這樣:
$\begin{align}
A_{1, 1}x_1 +& A_{1, 2}x_2 +& \cdots &&+ A_{1, N}x_N &= B_1 \newline
A_{2, 1}x_1 +& A_{2, 2}x_2 +& \cdots &&+ A_{2, N}x_N &= B_2 \newline
& \vdots & \ddots & && \vdots \newline
A_{N, 1}x_1 +& A_{N, 2}x_2 +& \cdots &&+ A_{N, N}x_N &= B_N \newline
\end{align}$
其中$A_{i,j}$和$B_i$都是常數。已知它恰有一組解,你能不能求出正確的$x_i$使上面每一條式子都成立呢?

Input Format

輸入第一行有一個正整數$T$,代表測資筆數。
對於每筆測資,第一行會有一個正整數$N$,代表你要解$N$元一次方程組。
接下來$N$行,每行有$N+1$個整數,第$i$行的數為$A_{i,1}, A_{i,2},\cdots ,A_{i,N-1},A_{i,N},B_i$。

對於所有測資,$T\leq 5; N\leq 600; |A_{i,j}|,|B_i|\leq 10^ 5$。

子任務(測資)額外限制分數
1(0~2)$N=1$5
2(0~5)$N\leq 2$17
3(0~8)$N\leq 3$22
4(0~11)$N\leq 5$43
5(0~14)$N\leq 20$13
6(0~17)$N\leq 80$16
7(0~20)$N\leq 200$17
8(0~23)無限制17

Output Format

對每筆測資請輸出$N$行,每行輸出一個浮點數(可以科學記號表示,如2.135e+7),第$i$行代表$x_i$的解。

考量到可能會有計算誤差,只要你輸出的$x_i$,對於方程組的每條式子,都有等號左右的相對或絕對誤差不超過$N\times 10^ {-7}$,就會被視為正確。

保證解的$|x_i|\leq 10^ 6$。

Sample Input

2
3
2 7 9 6
8 9 7 6
2 6 5 3
1
3 3

Sample Output

0.3829787234000
-3.191489362e-1
0.829787234
1

Hints

Problem Source

Problem Set / Description by Yihda Yol
建國中學106學年度校隊補選pA

Subtasks

For Testdata: 0 ~ 2, Score: 5
For Testdata: 0 ~ 5, Score: 17
For Testdata: 0 ~ 8, Score: 22
For Testdata: 0 ~ 11, Score: 43
For Testdata: 0 ~ 14, Score: 13
For Testdata: 0 ~ 17, Score: 16
For Testdata: 0 ~ 20, Score: 17
For Testdata: 0 ~ 23, Score: 17
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 262144 262144
1 1500 262144 262144
2 1500 262144 262144
3 1500 262144 262144
4 1500 262144 262144
5 1500 262144 262144
6 1500 262144 262144
7 1500 262144 262144
8 1500 262144 262144
9 1500 262144 262144
10 1500 262144 262144
11 1500 262144 262144
12 1500 262144 262144
13 1500 262144 262144
14 1500 262144 262144
15 1500 262144 262144
16 1500 262144 262144
17 1500 262144 262144
18 2500 262144 262144
19 2500 262144 262144
20 2500 262144 262144
21 3500 262144 262144
22 3500 262144 262144
23 5000 262144 262144