TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

88.2% (15/17)

Submission's AC Ratio

49.6% (59/119)

Tags

Description

  公元3210年,人類已經可以移居到其他行星了。人類也發展出了傳送器,可以將任何東西立即傳送到任何指定的地方。但傳送是非常消耗能源的,因此基於環保的概念,星際聯邦定出了每人每日只能傳送一次的規定。但由於每個星球的自轉速率不同,所以一天的時間也不一樣長,星際度量衡大會基於星球自治的觀點,除了「時」、「分」、「秒」是絕對單位,以及「日」是有定義的單位以外,每個星球都可以自訂曆法。

  而「日」的定義為:「在黃道面上挑一個基準點,太陽光兩次直射基準點之間的時間」,所以各個星球的「一日」都不一樣長。
(黃道面的定義是星球公轉軌道的平面,太陽的定義為星球所繞的恆星)

這裡為了簡化問題,有以下的假設:


  • 沒有聯星系統也沒有聚星系統(也就是不會有兩個以上的星球互相繞著共同的重心旋轉,也不會有恆星繞著恆星轉的情況),且一個星系中只會有一個恆星。
  • 行星的公轉軌道是圓形,且處於一個通過太陽的絕對平面上。
  • 任何一個星球都是圓球。
  • 星球的公轉和自轉週期是定值。

在地球上有一個名數學家叫做上卜因心,他總共做了N趟星際旅行,去過的星球也剛好是N個,每次去一個星球都會剛好停留在那個星球一日,每趟旅程都會記錄從地球出發的時間和回到地球的時間,現在他想要用這些資料推算出那N個星球的自轉週期,所以他寫了一封信請你幫他寫一個程式解決這個問題。

下面是上卜因心附上的簽名影本。

Input Format

輸入檔的第一行有一個正整數K,代表上卜因心總共給你K份旅遊記錄(K<=20)(由於你不知道哪份才是他真正的旅遊記錄,所以你必須每份都處理)。

每份旅遊記錄的第一行有一個正整數N,接下來有N行,第一個數字是一個正整數M,代表他這趟旅行總共去了M個星球,接下來有M個整數,依序代表了他去的星球的編號(他將他旅行過的星球分別編號為 0 ~ N-1 ),最後有一個正整數D,代表他這趟旅行從出發到回來地球上總共過了D天,D <= 365。

對於每份旅遊記錄你都可以做以下的假設:

  • 0 < N <= 20。
  • 同一趟旅程不會經過同樣的星球。
  • 每個星球的自轉週期都是地球的整數倍。
  • 上卜因心給的資料一定能推算出那N個星球的自轉週期。

Output Format

對每份旅遊記錄輸出N行數字,代表編號 0 ~ N-1 的星球的自轉週期為地球的幾倍(不需加單位)。

Sample Input 1

2
2
1 0 17
1 1 14
3
2 0 1 19
2 0 2 16
2 1 2 13

Sample Output 1

17
14
11
8
5

Hints

Problem Source

原TIOJ1138 / 96 TWN Practice Contest 1。Problem Setter: TDYa127。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1