TopCoder

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

53.7% (22/41)

Description

傳說17世紀著名的海盜船長基德曾將搶來一筆巨額財產藏匿在某無名小島上的洞穴中。
因為是筆龐大的財富,所以在他死後,世界各地的寶藏探險家都想找到他寶藏的藏匿之處。
但傳說因為基德船長怨靈的詛咒,進入洞穴的人都難逃一死,至今還沒有人活著出來過!
因為恐懼,慢慢的大家不再提起這批寶藏,而寶藏的謎一直延續到現在。

傑克船長是一知名的寶藏探險家,至今已經找到許多傳說中藏匿的寶藏。
某一天,傑克在酒吧裡因緣際會地得到這筆寶藏的藏寶圖,藏寶圖上除了揭露寶藏的所在地外還有一串由0與1組成的奇怪數字串。
傑克船長於是根據藏寶圖率領他的船員順利地找到這無名的小島並進入洞穴中,最後抵達寶藏藏匿的地點。
但他們卻發現藏匿寶藏的地點有無數道門,而每一扇門上都有一串奇怪的數列(包含0與1以外的其他整數值,整數之間有空格間隔)。
而從白骨遍地的情景來推斷,這些門之中可能只有一扇門中有真正的寶藏,只有找對那扇門才能順利取得寶藏;
而若開錯門,可能會引來殺身之禍!

傑克船長幾經推敲,終於發現門上的數列跟藏寶圖上的0、1數字串有某種關連,
於是他將解法教給他的船員,要他們找出正確的門是哪一扇門。
聰明的你(妳),請幫助傑克船長的船員,寫一組程式算出看看哪一扇門後才是真正藏有寶藏,使他們能順利地取得寶藏!

解法說明
例如,有3扇門,門上的數字串如下:
27 13 45 57 30
3 7 21 30 81
20 42 61 123 145

藏寶圖上提示密碼為:
0 1 0 1

解法過程
(1) 先解第一扇門的數字串27 13 45 57 30
(2) 由後往前(即右往左)推算,最後兩個數字先比大小,後面大於等於前面則為1,反之為0。
(3) 30 < 57→ 0
(4) 接著後兩個數字相減的值取絕對值跟第三個數字比大小,若大於等於第三個數字為1,反之為0。
(5) 30–57 = -27,取絕對值為27 < 45 → 0
(6) 以此類推,若前面已無數字可比,則結束。
(7) 57–45 = 12 < 13 → 0
(8) 45–13 = 32 > 27 → 1
(9) 所以27 13 45 57 30對應的0、1數字串為1 0 0 0
(10) 同樣推算出第二串與第三串數字對應的0、1數字串
(11) 3 7 21 30 81 → 1 1 1 1
(12) 20 42 61 123 145 → 0 1 0 1
(13) 三扇門的數字串中唯一與提示密碼0 1 0 1符合者為20 42 61 123 145,則此一扇門後即是真正藏有寶藏。

Input Format

輸入檔案中的第一行為兩正整數N與M,以空格隔開;
其中N表示門的個數,M代表地圖上的0、1數字串的個數。
第二行為一串由0、1組成的數字串,以空格隔開,為提示密碼。
接著有N行,每一行對應某一扇門的數字串、數字間一樣以空格隔開,這N行中有一行的數字串為正確解答。

Output Format

輸出正確解答的數字串,以空格隔開。

Sample Input

輸入檔範例 1
2 2
0 0
3 5 4
12 45 47

輸入檔範例 2
3 4
0 1 0 1
27 13 45 57 30
3 7 21 30 81
20 42 61 123 145

Sample Output

輸出檔範例 1
3 5 4

輸出檔範例 2
20 42 61 123 145

Hints

Problem Source

原TIOJ1680 / 98北市賽(prob 4)

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5