101 . 超時空跳躍

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

44.4% (4/9)

Tags

2021 高階競技程式設計 - Contest #3

Description

時間來到第四次 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！

Input Format

第一行給定一個整數 $N$ 代表總共有多少個世界線 ($2\leq N\leq 25$)

接下來 $N$ 行代表這 $N$ 個世界線的穿越的干涉係數，每行有 $N-1$ 個數代表該世界線穿越到其他世界線的干涉係數（自己穿越到自己等於沒變，所以不會出現)。

例如這 $N$ 行中的第二行的 $N-1$ 個數依序分別代表第 $2$ 個世界線穿越到如下

  • 第 $1$ 個數代表穿越到第 $1$ 個世界線的干涉係數
  • 第 $2$ 個數代表穿越到第 $3$ 個世界線的干涉係數
  • ...
  • 第 $N-1$ 個數代表穿越到第 $N$ 個世界線的干涉係數

依此類推，且 $0\leq 干涉係數 \leq 10^3$。

Output Format

如果可以找到一組變動率超過 $1.01$ 的世界線穿越法的話就輸出路徑，如果有多組的話要輸出路徑最短的那一組，如果找不到一組合法的穿越路線的話就輸出 go back go back，需要注意題目沒有要求變動率最大，只需要最終變動率達到 $1.01$ 以上且路徑最短的。

Sample Input 1

3
0.5 0.1
0.76 0.75
3 0.87

Sample Output 1

1 2 3 1

Sample Input 2

2
0.87
0.78

Sample Output 2

go back go back

Hints

嘟嘟嚕 ~

Problem Source

Subtasks

No. Testdata Range Score
1 0~56 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
33 1000 65536 65536 1
34 1000 65536 65536 1
35 1000 65536 65536 1
36 1000 65536 65536 1
37 1000 65536 65536 1
38 1000 65536 65536 1
39 1000 65536 65536 1
40 1000 65536 65536 1
41 1000 65536 65536 1
42 1000 65536 65536 1
43 1000 65536 65536 1
44 1000 65536 65536 1
45 1000 65536 65536 1
46 1000 65536 65536 1
47 1000 65536 65536 1
48 1000 65536 65536 1
49 1000 65536 65536 1
50 1000 65536 65536 1
51 1000 65536 65536 1
52 1000 65536 65536 1
53 1000 65536 65536 1
54 1000 65536 65536 1
55 1000 65536 65536 1
56 1000 65536 65536 1
Submit
Status
Ranklist
Back to Top