TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

39.6% (21/53)

Submission's AC Ratio

11.9% (74/624)

Tags

Description

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

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

所謂的N元一次方程組,長得像這樣:
A1,1x1+A1,2x2++A1,NxN=B1A2,1x1+A2,2x2++A2,NxN=B2AN,1x1+AN,2x2++AN,NxN=BN
其中Ai,jBi都是常數。已知它恰有一組解,你能不能求出正確的xi使上面每一條式子都成立呢?

Input Format

輸入第一行有一個正整數T,代表測資筆數。
對於每筆測資,第一行會有一個正整數N,代表你要解N元一次方程組。
接下來N行,每行有N+1個整數,第i行的數為Ai,1,Ai,2,,Ai,N1,Ai,N,Bi

對於所有測資,T5;N600;|Ai,j|,|Bi|105
保證由 Ai,j 所構成的矩陣中絕對值最大與最小的特徵值(eigenvalue)的比值 |λ1λN|103(白話地說,這組方程式不會太接近無解或沒有唯一解的方程式組)。

子任務(測資)額外限制分數
1(0~2)N=15
2(0~5)N217
3(0~8)N322
4(0~11)N543
5(0~14)N2013
6(0~17)N8016
7(0~20)N20017
8(0~23)無限制17

Output Format

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

考量到可能會有計算誤差,只要你輸出的xi,對於方程組的每條式子,都有等號左右的相對或絕對誤差不超過N×107,就會被視為正確。

保證解的|xi|106

Sample Input 1

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

Sample Output 1

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 (VSS, 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