Afutseng's Blog

競賽日期：2008/03/26

又到了一年一度的程式比賽，今年報名人數達 39 位，近去年的兩倍，不過獎金縮水了，各減兩千。

今年選在平日舉辦，只好特地請一天班來比賽呀，競賽時間是中午十二點半開始，四個小時。
賽前看到傳說中的新一代信長作者－炎羅的真面目，唔。。跟我想的有段差距啊。

今年的題目只有七題，難易度設定為簡單三題、中等與挑戰各兩題。

第一題是「計算重複的數字與次數」

有 n 個範圍在 1 ~ 99的整數，找出重複的數字及重複次數。
例如有九個整數是： 3, 2, 2, 12, 3, 2, 12, 99, 75，則依出現的順序輸出：
3:2 (意即 3 重複 2 次)
2:3
12:3
沒有重複的數字不輸出，若全部都沒有重複，則輸出 0 。

這題想當然是簡單之一了，就從第一題開始解起，雖然測資都正確了，不料送出後答案錯誤，使得我開始懷疑是不是輸入的問題，只好先改解第二題。害我剛送出的時候高興了一下。。（因為還沒有人解出任何題目。）

第二題是「撲克牌排序」

給定 13 張包含花色的撲克牌，花色和點數的定義如下：
花色定義：黑桃=S, 紅心=H, 方塊=D, 梅花=C
點數定義：A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
這題的要求是先依點數從 A 排至 K，若點數相同則依花色順序排列 ( 黑桃, 紅心, 方塊, 梅花 )。

解法是先定義一個撲克牌結構 ( struct )，存有花色與點數兩個成員變數，這樣寫起來會比較直覺。
讀入資料後就是本題的關鍵－排序，我寫了一個自訂的compare函式，處理四種花色的排序優先順序，再傳入 sort() 就解出了，此題應也為簡單層級之一的題目。
解完這題的時候只有少少人做出一題。

第三題是「四位數猜數字遊戲」

遊戲開始時，電腦選定一組數字不重複的四位數字，由使用者猜測電腦所選定的數字，電腦將以＊A＊B的訊息來回應猜測的數字是否正確。

範例一
電腦選定數字：1234
猜測：5283
回應訊息：1A1B，表示使用者猜對兩個數字，其一位置正確，另一個位置不對。

這題顯然是全部題目中最簡單的一題，賽後也確實是最多人解出這題。

此題解法只要兩層迴圈來檢查電腦選定數字及猜測數字即可。雖然這題很簡單，不過送出時不夠嚴謹，忘記用 getline() 的方式擷取整行輸入，以致得到了兩次格式錯誤。

第四題是「位數的乘積」

這題讀完題目初步判斷不好解，因此我跳過了。在解新題目之前，我先回過頭重新檢視第一題是否哪裡有問題，code 改的蠻亂的，可說是重寫了，還加上一些疑神疑鬼的檢查，不過仍然錯誤。只好擱著再解下一題。

第五題是「數字積木」

有 15 種數字形狀的積木 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F，分別代表十六進位的數字，注意沒有 0。若給予若干塊積木，將全部給予的積木排成一列則形成一個十六進位的數，當然不同的排列順序就形成不同的數。例如給予3, 7, D三塊積木，則可以排出 37D, 3D7, 73D, 7D3, D37, D73共六個十六進位的數。

這個問題是：給予若干積木（數字可能重複），每次排列都必須使用全部給予的積木，請算出總共可以排出多少個不同的十六進位的數是可被 5 整除的。

讀完題目雖然知道這題不難，但有幾樣工作要另外處理，必須花不少時間，由於題目要求出多少個排列可被 5 整除，因此需要十六進位轉十進位的函式，才能判斷。
C++似乎沒有內建的函式，只能自己寫，再來必須列出字串的所有排列，不過這個工作可以交給 next_permutation 解決，C++ 的 STL 函式庫真是好物啊！

很幸運地，第五題沒有任何錯誤就通過測試了，接著我又嘗試修正第一題，不過仍然徒勞無功，只得放棄這題了。

讀完第六、第七題後，因第七題是霍夫曼編碼問題，要用到樹狀結構，但我沒帶資料，時間也不夠用了，這題就不寫，最後就嘗試解第六題。

第六題是「羅馬數字求值」
這題我沒寫完，比賽結束，解出六題有一人（大四金門學長），也是去年的第一名。其次解出三題有一人，就是我啦，蟬聯第二名，算是預料中之事，畢竟 程式解題領域非我本行，使用的語言也不算熟悉，不過這次比去年進步，多解了一題（其實應該要可以解四題的），第一題在賽後去找裁判要測資，回家比對程式才發現敗在陣列大小，只要修改一個數字，我第一次繳交的程式碼就可以通過了，殘念啊。

解出二題的只有兩人，資訊管理系一年級的同學兩題解題時間都比資工的早，因此第三名落到外系手裡了，不知道算不算是給系上的警訊？
雖然這次參加人數增多了，主辦單位也祭出解兩題以上者，JAVA程式設計課程就可以加分，但程度與去年相較仍然沒有什麼進步，最後也沒人可以加到分。
比較可惜的是這次參賽的球球學弟，資工一年級，是該年級甲乙班程式程度最好的，可能因為緊張或是不熟悉此種程式解題比賽的輸入方式，僅解出一題。

賽後隔兩天就領到獎金了 ( $5200 )，辦事效率還挺高的，明年假若無意外，第一名就是到我身上了。