Monday, November 12, 2007

什麼是 ACM Problemset 以及如何註冊 ?

ACM是 Association for Computing Machinery 的縮寫,是世界上研究電腦科學的一個組織。而ACM Online Judge System 是由西班牙的一所大學維護,他裡面收集了許多歷年來ACM程式比賽的題目,讓有興趣的人去解題,藉由一些測試資料來判斷寫的程式正不正確,當然定期也有一些線上比賽可以參加。

為什麼要寫ACM呢?有些人常常會幻想說,我要寫遊戲!我要當駭客!我要成為海賊王之類的夢想。但是,夢想沒有努力去做,充其量也是幻想。這就像小鳥不會跳就想學飛是一樣的。有人會覺得寫這些題目沒什麼,很無聊、題目是英文看不懂,但是卻不知道這是訓練一個人用電腦解決問題的能力的方法,是一種磨練。

三分鐘熱度的人很多,會持續去寫的人很少。但是實際寫一陣子以後,不用說很強,也自然會發現學校的作業似乎不是這麼的難。又可以練習到資料結構、演算法、離散數學的能力。

講了這麼多,要開始之前,先好好想一想到底你真正想要的是什麼。不然也不必花時間註冊帳號,浪費自己的時間也浪費網路資源。

首先,開啟http://icpcres.ecs.baylor.edu/onlinejudge/



按下左方的Register,進入註冊畫面。



依序填入相關資訊(名稱、密碼,希望大家註冊時能夠加上NCCUCS的字樣),值得注意的是E-Mail請填一個平常會去看信的信箱,Online-Judge ID則是如果之前已經註冊過舊版的ACM帳號,就把之前的五碼數字加上兩碼英文填入,可以做資料的轉移。如果是新手則填入五個零00000,最後一個選項是選擇是否把解題的結果送到信箱。一切完成以後就可以按下Send Registration了。

完成之後就可以到你的信箱裡面收信,信裡面有個又臭又長的連結按下去,就可以成功啟用這個帳號了。

接下來將說明如何送出題目。首先我們先回到一開始的首頁從左邊登入自己的帳號密碼以後,會看到如下的畫面:

在Browse Problems上面按下去之後,右邊會出現兩個資料夾:Problem Set Volumes跟Contest Volumes。前者代表的是原本網站上面的題庫,編號是100~999;而後者則是歷年ACM比賽下來的題庫考古題,編號都是五位數的數字。



舉例來說,我現在要寫史上最簡單的題目10071,所以我會去Contest Volumes底下的Volume C找到10071 - Back to High School Physics (這邊資料夾是用羅馬數字來分類的,每一百題一個資料夾)。同時題目右邊的兩個百分比則代表了所有送出的CODE裡面有多少%是成功解出來的所有使用者裡面有多少%成功解出這題。由此可以知道此題的難易度如何。

現在點進去看題目,題目一開始扯了許多東西,像是一個粒子經過一段時間的加速會從初速V0跑到V的速度,題目問,如果一個粒子以V的速度跑了兩倍T的時間,位移是多少?夠簡單吧!

看題目時,要注意他規定的INPUT跟OUTPUT格式。以這題來說INPUT每行都是一組測試資料,分別是兩個數字代表V跟T(題目有給V和T的範圍),而OUTPUT則是一行代表一個結果,只要輸出數字就好,其他的文字都不必要輸出。像是什麼無關緊要的字串如:The Result is .... etc都不用,只要輸出題目要的東西即可。他會給一些SAMPLE的INPUT跟OUTPUT可以參考,但是可別以為這些對就會成功。因為其實有時候很多邏輯沒考慮到,而她給的SAMPLE也沒講出來,那麼貿然送出就可能會得到WA了。還有,所有的題目都是標準輸出輸入,所以不會用到讀檔的問題。

題目上方有三個按鈕分別是:送出、下載電子板的題目、跟這一題的統計資料(如:解出的人花的CPU TIME跟記憶體等等),假設現在我們寫好了就可以按下送出。



按下送出後會看到一個新的頁面,上面可以選擇用的程式語言(C、C++、JAVA、PASCAL,注意這些語言所使用的版本,像是C就是只能用ANSI C),選好以後可以在中間貼上CODE或者是從下面上傳檔案。當一切準備好,就可以按下送出了。


送出以後會跳到原本題目的頁面,不過上面會出現一個紅底的字樣寫著這次送出的編號。


記起來這個編號以後,可以點左邊的My Submissions去觀看結果。果然點下去以後,看到了這個編號送出的結果是Accepted,代表我們這題寫的是正確的,完全通過所有測試資料的結果。



一般來說,看到的結果會有下面這些:

Accepted(AC): 代表完全正確,格式也正確。
Presentation Error(PE): 結果正確,但是呈現的格式錯誤,ACM網站上面會算有解出這題,但正式比賽就不是了。
Wrong Answer(WA): 至少有一組的結果是錯誤的,但不會跟你說哪裡錯。
Runtime Error(RE): 執行階段錯誤,像是可能除以零。
Time Limit Exceed(TLE): 超過執行時間,一般來說每一題都是給十秒跑完所有測資,但是有些題目會指定時間。
Memory Limit Exceed(MLE): 同上,記憶體用太多了。
Output Limit Exceed(OLE): 輸出資料過多。
Compile Error(CE): 這更慘,COMPILE沒過,會把編譯器的錯誤訊息寄回信箱。
Restricted Function(RF): 使用一些禁制的函數,像是system()、檔案有關的函數等等。
Other: 其他種類錯誤。

簡單來說,看到Accepted就是成功解題的象徵。

ACM訓練的不只是分析題目,更考驗了邏輯、和許多數學的能力。慢慢的寫,從簡單開始到難題,實力是可以慢慢累積起來的。有興趣可以三五好友組成讀書會一起加油。

===============================================

附上10071的參考CODE:

#include <stdio.h>

int main(){
int v,t;
while(scanf("%d %d",&v,&t)==2){
printf("%d\n",2*v*t);
}
return 0;
}

[2F] 理學院鬼屋特別企劃

2F


2F理學院鬼屋特別企劃在11/09-11/10畫下了完美的句點。

在最後一組劉凱新繞場通知下,鬼屋正式結束了。大家都辛苦了,不論是活動開始前美宣的準備還是活動當天的工作人員。聽到有人在風雩樓裡面大喊,怎麼還沒走完,真的是還蠻有趣的。

當了兩天的女鬼,總是會有一些奇怪的事情。這就要從去租衣服開始說起了,西門町真是個神奇的地方,尤其是能夠租到我能塞進去的女用禮服那是更神奇了。不過也找了蠻久的,後來其實只要先試試看我的手能不能鑽過這條袖子就好了。簡單來說,心理系的阿冷姊姊的禮服是束腰,我這件根本就是在束胸。也許天天穿可以增加肺活量吧。

星期五的下午在幫忙場布,差點把老鼠撞飛,但我也很懷疑我手臂上的割傷是那時候出現的。第一天化妝當女鬼,大概是我生平以來第一次上過這麼濃的妝吧。然後因為又是傍晚開始,中餐卻吃很少,飢餓難耐。看到7-11的便當的時候竟然是這麼的美味,在遊客走了以後馬上從漆黑房間中的椅子下把便當拿出來,也不管會不會把妝吃下去,就開始狼吞虎嚥了,等到有人來馬上又藏起來就定位。這兩天沒戴眼鏡的夜生活,看的很累XD!不過死人沒有卸妝就搭綠一回家,這真有勇氣。不過我的臉前後洗了八次才洗掉...

第二天趕著下山,忘記多帶一件衣服可以換,剛好又穿了黑色吸一點汗就會臭的資科營服,然後剛好扮鬼的這個隔間是沒有什麼冷氣的。第二天早上畫的恐怖妝到中午就變滑稽妝了,不過暗暗的沒差。只是有個可惡的女遊客經過時,原本要嚇人的,卻聽到他說怎麼這裡感覺友汗臭味,害我差點整個笑場。等他們走了以後,恰恰竟然用帥氣的台中腔,在垃圾袋隔間外面的休息室大喊:哈哈,胖達好臭= =+!然後孫玫如好像從狗洞那邊經過我這邊也在笑,真悲慘。我猜在這一塊裡面扮鬼的人應該已經嗅覺疲勞了吧。下午換班的時候順便洗了一下衣服,後來改去別的地方嚇人。最後還跑去自己玩一次,感覺真的很讚。到五點的時候,真的是意猶未盡,於是又穿上戎裝﹝我是說女鬼禮服﹞,但是因為我已經卸妝了,所以這次就帶了面具﹝悲慘的另一個開始﹞。

五點之後大概是最多爆點的時候吧!因為每次來的人,幾乎都換梗,可能真的嚇人嚇上癮了,每次有一組經過以後就會開始想下一組要怎麼嚇他們。尤其是當有人來說下一組是劉凱新的時候,大家馬上都準備出最棒的好菜給他,像我整個就是抱著他走了XD!不過我猜這叫噁心,不是恐怖了。

拆道具的時候,才知道美宣黏東西黏的真緊,尤其是鐵絲。不過拆完道具以後,發現又多了一些神秘的撞傷= =!九點十點的時候一群人吃了世界大同,刀片在校門口玩弄校園導覽就是弄不出來某院爆炸,然後孫玫如隨便按隨便爆,整個就是很有趣。

回去以後整個就是很累,可是還是很不要命的聊天,因為實在太有趣了,所以我就來寫一些有趣的人物好了。首先,真的沒在現場一定不會相信,真的有男生進去比女生還娘的。嚇到跌倒的、還有沿路在喊媽媽的、連續跌倒兩次的。不過當然也是會有一些所謂的澳客,到處跟其他人說這裡有個人,不然就是我猜她待會會動等等。整體來說,當鬼的時候聽到前面那一關的人尖叫不停,我們就會比較努力的嚇人,澳客就不理他了。當然後來聽他們的尖叫聲都覺得好笑,感覺超誇張的。

誇張的可多了,第一天有一個媽媽帶著他的兒子來,嚇到一路在那邊喊:妳是哪個系的,我要跟你們院長講。還有前面那個說我很臭的。還有一個該死的男生,走過去跟我說:這位小姐您真壯碩。多麼傷感情的一句話啊...還有一組的一個人可能是被嚇到,我第二天戴面具,他被嚇到的時候竟然把手指往我嘴巴裡面插,雖然沒有很大力,然後我又以為可能是壓隊的工作人員在打招呼﹝他走很後面,我沒戴眼鏡﹞,所以我就很自然的左手揮下去。然後那個女生就嚇一跳,然後一直跟前面的那個男生說:欸,他打我屁股耶!欸,他打我屁股耶!......笑死Orz。還有小紅帽,一路叫,看到我也在叫XD,相對於他前面的MURMUR吳,實在是相差甚遠!不過一個一路MURMUR,一個一路叫也蠻有趣的。

的確,嚇人真的嚇上癮了。不過我猜,這應該是大學的最後一個活動了吧!

來幾張圖好了。既然是歌劇社,那就來個歌劇魅影。
歌劇魅影 Eric and Christine


五六組的一些組員
一些鬼!?


另外我真的很佩服阿冷姊姊可以當兩天的鬼都不換班,然後衣服還被嚇到的人扯到。然後還有第五組的梗學妹,在租衣服的路上,一路爆梗,真是太好笑了。