時間來到第四次 contest 前夕,小嵐因為想不出比賽題目所以穿越世界線跑路了,而為了不要比賽開天窗少了一場成績讓自己被當掉,所以競程學員們傾巢而出勢必要把小嵐抓回來繼續出題。
在這世界有這樣一個規律,每個世界線的初始變動率都是 $1$,但只要小嵐發出一封 D-Mail 穿越世界線的話,世界變動率就會跟著改動,改變後的值為原本變動率乘上給定的干涉係數,而在穿越眾多世界線回到原本的世界線並且世界變動率達到了 $1.01$ 以上才是小嵐要尋找的那個不用出題的世界線。
例如現在選定起點為世界線 $1$,且已知從世界線 $1$ 穿越到世界線 $2$ 干涉係數為 $0.5$,世界線 $2$ 穿越到世界線 $3$ 干涉係數為 $0.75$,世界線 $3$ 穿越到世界線 $1$ 干涉係數為 $3.0$,那麼從世界線 $1$ 穿越一輪回到世界線 $1$ 得到的世界變動率就是 $1\times0.5\times0.75\times3.0=1.125$,這就是小嵐要尋找的不用出題的世界線,也就是命運石之門線,需要注意的是穿越世界線的次數不能超過世界線的總數,像是這邊的例子就是穿越三次,如果超過的話就會迷失在 R 世界線,在那個世界線裡小嵐每天都要出 10 場 contest 的題目。
小嵐可以自由選定起始穿越的世界線,而且小嵐有一張每個世界線互相穿越的干涉係數表,為了可以成功逃離世界線收束成他要出題的未來,所以他把找出如何穿越世界線達成目的的任務交給你了,El Psy Congroo!
第一行給定一個整數 $N$ 代表總共有多少個世界線 ($2\leq N\leq 25$)
接下來 $N$ 行代表這 $N$ 個世界線的穿越的干涉係數,每行有 $N-1$ 個數代表該世界線穿越到其他世界線的干涉係數(自己穿越到自己等於沒變,所以不會出現)。
例如這 $N$ 行中的第二行的 $N-1$ 個數依序分別代表第 $2$ 個世界線穿越到如下
依此類推,且 $0\leq 干涉係數 \leq 10^3$。
如果可以找到一組變動率超過 $1.01$ 的世界線穿越法的話就輸出路徑,如果有多組的話要輸出路徑最短的那一組,如果找不到一組合法的穿越路線的話就輸出 go back go back
,需要注意題目沒有要求變動率最大,只需要最終變動率達到 $1.01$ 以上且路徑最短的。
嘟嘟嚕 ~
No. | Testdata Range | Score |
---|---|---|
1 | 0~56 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 | |
37 | 1000 | 65536 | 65536 | |
38 | 1000 | 65536 | 65536 | |
39 | 1000 | 65536 | 65536 | |
40 | 1000 | 65536 | 65536 | |
41 | 1000 | 65536 | 65536 | |
42 | 1000 | 65536 | 65536 | |
43 | 1000 | 65536 | 65536 | |
44 | 1000 | 65536 | 65536 | |
45 | 1000 | 65536 | 65536 | |
46 | 1000 | 65536 | 65536 | |
47 | 1000 | 65536 | 65536 | |
48 | 1000 | 65536 | 65536 | |
49 | 1000 | 65536 | 65536 | |
50 | 1000 | 65536 | 65536 | |
51 | 1000 | 65536 | 65536 | |
52 | 1000 | 65536 | 65536 | |
53 | 1000 | 65536 | 65536 | |
54 | 1000 | 65536 | 65536 | |
55 | 1000 | 65536 | 65536 | |
56 | 1000 | 65536 | 65536 |