TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

42.9% (12/28)

Submission's AC Ratio

11.5% (37/321)

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

No. Testdata Range Score
1 0~2 5
2 0~5 17
3 0~8 22
4 0~11 43
5 0~14 13
6 0~17 16
7 0~20 17
8 0~23 17

Testdata and Limits

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