2004 IPSC result
YSL 又輸了。在當天才得知晚上要比 IPSC 的情況下,我們蹺掉了錯誤更正碼,前往 SBB 家準備再創佳績。
A 是給你兩個程式以及 output ,要你找出他的 input 。 A1.in Lwms 馬上看出來這是個 Discrete Logarithm Problem ,所以寫了個小程式跑出來,但是有一組測資數目實在太大,跑不出來,我密碼學的書又放在家裡面,最後卻神奇地發現解答… accept!
B 是問你 NxN 的西洋棋盤上能放幾個 Bishop ,Lwms 直覺地猜是 2N – 2,結果 B2 卻被婊到了,因為當 N = 1 時能放 1 個。最後發現,對了。
C 的題目我們好像一直誤解,所以根本沒做出來。
D 是互動題,做 optimal search 猜數字。你每次猜一個數字,他會回答你大於小於或等於。但值得注意的是,他回答的是你的前 n 個提問。也就是說,你每次問他並不會立刻回答,而是在下 n 個回合他才會回答你這個問題的答案。舉例:
You -> Mincer: 3
Mincer -> You: There is one Meat inside
You -> Mincer: 5
Mincer -> You: There are two Meats inside
You -> Mincer: 4
Mincer -> You: Mincer full, output: “My number is GREATER than 3”
You -> Mincer: 32
Mincer -> You: Mincer full, output: “My number is SMALLER than 5”
You -> Mincer: 51
Mincer -> You: Mincer full, output: “You’re RIGHT, it’s 4”
這題他們的 Mail Server 被搞掛了,我們雖然對了 D1 ,但是 D2 卻遲遲等不到回答。含恨而終。
E 我完全不知道題目是啥,不予置評。
F 是超難題,給你一個水管的孔徑,這根水管裡有許多直徑不同的棒子,各有各的起點終點,問你一顆球從水管上丟進去可不可以從另外一邊滾出來。
G 是我做的,給一個很機八的程式語言,只有一個 queue 和 26 個 register 。而且所有運算都只能在 queue 上作用,register 之間不能 assign ,要用這語言寫程式的困難之處在於你做了個運算沒有辦法立刻知道結果,你只能把結果丟回 queue 裡面,但是這個 queue 裡面又有不知道多少亂七八糟的資料,你沒辦法知道讀到什麼時候才能停止。所以沒有辦法依據運算後的結果來做判斷。題目要你用這個語言寫兩個程式,第一是個 sort 程式,第二是個印出自己程式碼(self-reproduce)的程式。sort 程式大概花了我一個多小時,我本來想用 bubble sort ,但是立刻遇到問題。在浪費一個小時都解決不了的情況下,我改用 selection sort ,總算寫出來。G2 我本來想利用 Recursion Theorem 的,但 SBB 家沒有課本,所以我只好自己想。幸好 IOCCC 的程式碼看多了,這題出乎意料的簡單,大概只花 10 分鐘。
H 這題題目完全誤解!比賽剛開始, Lwms 看過這題後就瞬間告訴我,這題是給一個多邊形還有很多很多矩形,問這些矩形能不能把多邊形蓋滿。聽到這句話我腦中浮現的就是矩形可以旋轉,要蓋一個多邊形。OK, 這問題實在太難了!跳過。後來一看,怎麼會是給矩形座標?而且還是平行於x, y 軸的。這樣子就簡單很多了!我們就寫一個程式可以畫圖,把多邊形畫出來以後用矩形擦掉,看能不能全都擦乾淨。但是因為很智障的因素,我們必須手動把每一個測資拷貝到程式碼裡面,於是做完 H1 後只剩 5 分鐘左右,就放棄 D2 了。但是比賽後重新看一下題目,題目意思根本和我們的理解不一樣。他給的矩形是互斥的!而且是問「能不能剛好嵌在多邊形裡面」,這和蓋滿截然不同!然而我們的 H1 竟然對了,也是神奇啊…
此時我們 83 名,台灣第三。接下來因為 D 的伺服器有問題,所以延長加賽一題 I 。題目和 D 完全一樣,如果對了,就當作 D 那題對。結果 Lwms 在解 I 時因為勢在必得太大意,最後陷入了玩樂心態浪費 submission,我們剛好差一個 submission 才能答對,令人扼腕。原本有望前進台灣第二,結果敗了,還被其他答對的人擠下去,變成 88 名,台灣第三。
Our Grades:
88. | YSL | 9 | 1422 | A1 B1* B2** D1**··(21) G1 G2 H1 |