上星期六我們前往師範大學
參加97學年全國大專電腦軟體設計競賽甲組比賽(簡稱大甲)
可能是去年黃金雄教授宣傳的關係
參賽隊伍比去年多,北區共有78隊參賽
今年我們學校總共有四隊報名(以往僅一隊)
我跟阿業、阿維一隊,阿良、王品、厚諭一隊
還有資三A的學弟妹兩隊

大甲算是ACM的前哨戰,比賽方式跟ACM相同
不但不需要報名費,還附贈一個便當
而且比賽前三名的隊伍還可以免費參加ACM競賽
但我們其實只是去玩玩的
因為我們這一年根本沒有花時間去解題庫
而他考的題型其實也很偏頗
一般學校的課程對這場比賽幾乎沒有幫助
所以我們一開始就不覺得自己會得獎,只是去玩玩的而已

大甲跟ACM的比賽有些規定很嚴格
比方說不准帶任何電子產品,像是電子字典、PDA、筆記型電腦
甚至連計算機都不可以(不太懂為什麼要這樣規定)
手機只要有響就直接失格,好像在考指考
阿良那組沒有在比賽前看過規定,導致他們三位完全沒帶字典
不過這次的單字都不怎麼難
我比到最後也沒翻過字典,真是白帶了

比賽的機器使用中文版的Debian,附有文字編輯器gedit
早上會讓你測機並給予兩道題目來解題
第一題是讀取字串,並將讀取到的陣列的所有元素反過來
如果裡面元素是字串的話也要一併反過來
老實說這跟去年阿業參賽時的練習題目相同
可是很離譜的,我竟然沒有寫出來="=
因為編譯一直出現奇怪的error
而且由於此題沒有先指定陣列數跟裡面的元素數
做起來相對麻煩(正式題目會跟你說要讀幾個元素)
第二題很簡單,讀取數字後判斷大小再印出相對的字而已
我前一天應該要練習C語言才是...

吃完供應的便當後(聽阿業說去年還附養樂多,今年卻沒了)
從12:30開始進行為期5個小時的比賽
比賽跟ACM相同,總共有十題,全英文出題
題目還會限制執行時間,就算答案對但執行時間超過一樣算錯
每答對一題工作人員會在你的電腦上掛上一顆氣球
所以看到別組的氣球就能知道他們答對題數(還能給予壓力)

我跟阿業、阿維各拿了一題來看
他拿了需要組合的數學題,我拿了老鼠走迷宮,阿維拿了解密題
其實我一直不會寫老鼠走迷宮的題目
但我很久以前曾經有印老鼠走迷宮的解法
在現場看了一下後,竟然就完全了解了=__=(人的潛力真是無窮)

不過阿維的解密題比較簡單
於是我們先解了解密題

Problem J
---------------------

從A到Z加上空白、句點、逗點共29個字母
用二進位給予00000到11100的編號
當某位置二進位為1時,將12345678最後面的字元移到該位置
比方說g為00110,就把12345678變成12873456
題目會給予你很多這8位數字,必須將他轉回英文字

此外,每個字元可以有+-1的誤差
比方說o為18762345,當輸入為27753244一樣要輸出o
範例輸入中出現*要換行,出現0則結束
最後還要印出共有幾個字元(*算一個字元,0不算)

Time Limit:1 sec.

Sample Input
128763451283456718276345182763451876234587612345871623458
17623451876234581237456182763451238745687165234*228853462
284356828285346282853462875134677621346771513467175134628
751346712484552828534622378455771562330

Output for the Sample Input
hello, world.
hello, world.
Total: 27 characters.


看起來很簡單?其實我一開始也是這麼認為的
這題要做對絕對不難,只要先把所有字元代表的數字輸入進去
再設一個數字陣列,判斷讀取到的字元是否符合字元代表的數字
若數字不符合就把陣列設0代表沒用,之後就不看他了
我一看到題目,腦海中馬上就想到這種解法

但...你有看到本題限制時間是幾秒嗎?是一秒!
要是用我這種方法的話,保證超時算錯
聽說學弟那組就是用這種方法的
幸好當時阿維想到了一種方法,只要判斷前五個字元即可
若是字元是大數則代表二進位為1,小數則為0
比方說81273456就是10010(注意:判斷大數會隨著抓到的數字做變動)
再把10010轉成十進位,就能把第18個字元s抓出來
這個方法要判斷的數字從8個減少到5個,的確是非常好

當時我腦筋還轉不過來,聽不太懂阿維的想法
不過後來了解之後,才發現他的作法~非常好!
因為我當時太緊張的緣故(加上冷氣口朝我吹)
還不小心把字元數算錯,被回傳wrong answer
害阿維緊張了一下,真是對他不好意思
第二次回傳後就顯示正確了

呼~要解一題還真是困難重重呢~

To be continued...

arrow
arrow
    全站熱搜

    蕭雲 發表在 痞客邦 留言(1) 人氣()