TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

84.3% (43/51)

Submission's AC Ratio

33.1% (97/293)

Tags

Description

  小光是個勤勞的考古地質學家,他致力於蒐集各處的地層,用儀器分析年份,然後把當地的歷史演進、生物的遷徙和演化用考古學和地質學的眼光重新描繪出來。小光常常出遠門到處採集樣本,他每到一個有完整的地層帶的地方,就會把整個地層從上到下每隔一段距離就採一個樣本,記好順序之後帶實驗室用儀器來測定年份。大部份的情況之下,因為樣本的採集是從上到下的,所以以越古老的地層會在越下面的原則,大部份的情況下先採集到的樣本年份會比後採集到的來得大,例如最先採集到的可能是公元1300年的沉積物,而最後採集到的可能是公元150年的化石。只是有時候因為地層變動,或者是取樣當地曾經被人為破壞過,又或者其實他用來測定年份的那個儀器也相當舊了,所以常常會發現有先採出的樣本竟然會比後採出的樣本還要古老的情形。為了解決這個問題,小光想到了一個辦法,他在同一個斷層採集兩次的樣本。這時候,兩者除了年份都要從新到舊的順序排之外,兩組資料勢必也要有年份相同相對應的樣本。此外也希望在比對之後符合上數條件的樣本數能取到盡可能的多。舉個例子:第一個樣本的年份是: 1941, 1762, 1853, 1433, 1100, 833;第二個樣本的年份則是:1762, 1941, 1553, 1853, 1100, 833。如此一來,可以確信的地層樣本應該要是:1941, 1853, 1100, 833。(雖然取1941, 1100, 833也是一個可能的答案,但是它所剩的資料數比較少,所以我們不予考慮)。

  小光昨天剛從美國某個峽谷採了一些樣本回來,可是因為旅途勞累、身體不舒服,沒有辦法整理他帶回來的資料。他知道你會寫程式解決問題,所以希望你幫他寫一個程式,只要他把年份輸入進去,就可以知道當地的地層年份的變化的資料。你能幫上他這個忙嗎?

Input Format

輸入檔的第一行只有一個數字 $N$ ,代表總共有幾筆資料。每筆資料由三行組成,其中第一行是樣本個數($5 \le S \le 512$ )。第二行和第三行分別有 $S$ 個數字表示樣本的年份。每個數字間以一個空白格開。

Output Format

對於每一筆輸入的地層資料,將可確信的結果印在同一行,其中各個數字要以一個空格隔開。你可以確定答案一定是唯一的,所以不用考慮如果有兩種選擇都可以時要印哪一個答案的問題。

Sample Input 1

2
6
1941 1762 1853 1433 1100 833
1762 1941 1553 1853 1100 833
6
1941 1762 1853 1433 1100 833
1762 1941 1853 1433 1100 833

Sample Output 1

1941 1853 1100 833
1941 1853 1433 1100 833

Hints

你可以假設沒有任何一次的樣本採集當中出現兩個年份相同的樣本。

Problem Source

原TIOJ1051 / NPSC2003決賽(prob G)

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

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