葉正聖

CHAPTER1程式能力檢定簡介

1.1 ACM國際大學程式競賽

ACM ICPC（International Collegiate Programming Contest，國際大學程式競賽）是由 ACM（Association for Computing Machinery，國際計算機器協會）主辦的一年一次程式設計競賽。藉由競賽方式來展現大學生創新能力、團隊精神，以及在壓力下編寫程式、分析和解決問題的能力。自從1970年代開創以來，經過三十多年的發展，ACM ICPC已成為全球電腦界中歷史最悠久且最具影響力的程式競賽。以2011至2012年為例，參加各地區域賽的隊伍超過8000隊，涵蓋88個國家及超過2000所大學。區域賽優勝隊伍會再集中於一處參與世界總決賽的競逐。以下列舉ACM ICPC的重要里程碑：

• 1970年：美國Texas A&M University大學程式設計比賽。

• 1977年：第一次舉辦世界總決賽。

• 1977至1989年：參與比賽的大學主要來自美國與加拿大。

• 1989年：建立區域賽(regional)制度，優勝隊伍才能參加世界總決賽。

• 1991年：亞洲首支隊伍（台灣交通大學）參加世界總決賽。

• 1995年：首度舉辦亞洲區域，並在台灣舉行，由國立政治大學辦理。

• 1996年以前：歷年贊助廠商依序為Apple、AT&T和Microsoft。

• 1997年之後：IBM公司為此競賽的主要贊助商。

• 1997年：參賽隊伍1100隊，來自560個大學。總決賽地點在美國聖荷西，代表台灣的台灣大學榮獲總決賽第4名，這是台灣隊伍首次進入前十名。

• 2002年：中國的隊伍首度獲得總決賽冠軍——上海交通大學。

• 2010年：參賽隊伍7900隊，台灣的隊伍獲得有史以來最好的成績，為總決賽第三名——台灣大學。

• 2011年：世界總決賽原訂於埃及沙姆沙伊赫舉行，但由於埃及當時發生暴動，因而將總決賽地點更換為美國奧蘭多。

自1997年以來的參賽隊伍數量與冠軍隊伍，詳列於表1.1。

表1.2、表1.3與表1.4分別列出2010年、2011年與2012年世界總決賽排名較為前面的隊伍。2010年前13名的隊伍，俄羅斯與中國合計佔了9個；2011年前12名的隊伍，俄羅斯與中國合計佔了7個；2012年前12名的隊伍，俄羅斯與中國合計佔了6個。由此可以看出世界頂尖的優秀隊伍超過半數集中於俄羅斯與中國，代表這兩個國家對於程式設計的能力非常重視。

1.2 ACM ICPC題目庫

ACM ICPC舉行三十餘年，所累積的寶貴資源，就是歷次的比賽題目。有些題目已經收錄於UVa線上評審網站（UVa online judge，網址為http://uva.onlinejudge.org/，其中UVa乃指西班牙瓦拉多利大學(Universidad de Valladolid)），目前累積已經超過3600題。全世界各地有許多人士在其上註冊帳號，進行練習，以提升程式設計能力。

該網站也會列出各題被解決的情形，以便讓人區分難易程度，如圖 1.1所示。中間的部分代表所有送出的程式碼被線上評審伺服器認可為正確的比例。由於線上評審伺服器可隨時評審程式碼，故使用者對於尚未被評審認可的程式碼可以再次遞送，直到正確為止。圖的最右側代表該題最後遞送出正確程式碼的使用者比例。

所有ACM ICPC題目均有固定格式，每題包含General Description（一般描述）、Input Format（輸入格式）、Output Format（輸出格式）、Sample Input（輸入範例）、Sample Output（輸出範例）共五大部分。每題長度大約一至三頁左右。圖1.2為題目範例。

雖然收錄於UVa網站的ACM ICPC題目庫，對於每一題均有遞送正確程式碼的百分比，以及正確解題的使用者百分比，但仍不足以完全分辨其難易程度。我們為了讓學習者可以瞭解適合練習的題目，並讓教師可以配合授課課程內容做為學生之實作或測驗題目，乃將題目區分為五個等級，如下所示：

• 一顆星(level 1)：學習完計算機概論之後即可解答（專家級設計師大約可於10分鐘撰寫完畢）。

• 兩顆星(level 2)：學習完資料結構之後才能解答或是苦工題（專家級設計師大約可於10至30分鐘撰寫完畢）。

• 三顆星(level 3)：需良好的演算法或數學方法才能解答（專家級設計師大約可於30至100分鐘撰寫完畢）。

• 四顆星(level 4)：需要特殊的演算法或是綜合多種演算法才能解答（專家級設計師需要超過100分鐘才能撰寫完畢）。

• 五顆星(level 5)：超越四顆星的極特殊題目。

1.3 大學程式能力檢定(CPE)

「ACM亞洲區台灣賽區大專程式設計競賽」自1995年起，每年在台灣各大學輪流舉行。為了提升國內大學生的程式設計能力，各大學相關科系的教授於2008年組織了「國際計算機器協會程式競賽台灣協會」（ACM-ICPC Contest Council for Taiwan，簡稱ACM-ICPC Taiwan Council），做為跨校交流與合作的平台。該協會下設三個委員會如下：

1. 推動委員會：負責資源與庶務之整合，原則上由參與學校之計算機中心（或等同單位）主任或資訊系系主任組成。

2. 技術委員會：由教練與命題老師組成，負責培訓與命題事務，原則上成員須具備程式培訓與命題之能力與經驗。

3. 大學程式能力檢定委員會（Collegiate Programming Examination Committee，簡稱CPE Committee）：共同舉辦CPE程式檢定考試，由已參與及即將參與舉辦CPE檢定考試之學校代表參加，該學校代表原則上為該校考場負責人。

大學程式能力檢定（Collegiate Programming Examination，簡稱CPE）旨在提升全台灣學生的程式設計能力，由學生透過線上程式設計，利用電腦自動評判，以檢測程式設計能力。CPE每年辦理四次，大約為每年的3、6、9、12月。CPE採電腦現場上機考試，以電腦自動評判，並由各校派員監考。考試時，會封閉與考試無關的網路。考生除紙本字典外，不能攜帶任何資料。考生若為大專學生，可免費報名。CPE的標誌如圖1.3所示。



UVa題目庫收集ACM ICPC國際競賽題目，是個相當龐大的題目庫。目前CPE的題目並非原創，而是選自ACM ICPC題庫。經由上述對於題目難易程度的分級，我們可以組合出適合的考題。每次CPE考試都會有簡單與困難的題目。

表1.5整理了自2010年開始舉辦CPE以來之歷次考生人數與答對題數統計資料。歷次參與辦理CPE的學校如下（依筆畫順序排序，第一次參與時畫底線）：

1. 2010/6/9，2校：中山大學、交通大學。

2. 2010/10/11，6校：中山大學、中央大學、台中教育大學、交通大學、長庚大學、輔仁大學。

3. 2010/12/23，9校：中山大學、中央大學、台中教育大學、交通大學、清華大學、清雲科大、慈濟大學、嘉義大學、輔仁大學。

4. 2011/5/25，19 校：中山大學、中央大學、元智大學、台中教育大學、台北大學、台南大學、交通大學、成功大學、東華大學、虎尾科技大學、長庚大學、清華大學、逢甲大學、慈濟大學、嘉義大學、暨南大學、輔仁大學、銘傳大學、靜宜大學。

5. 2011/9/27，17 校：中山大學、中正大學、中興大學、元智大學、台中教育大學、台北大學、台南大學、交通大學、成功大學、虎尾科技大學、屏東教育大學、逢甲大學、嘉義大學、暨南大學、輔仁大學、銘傳大學、靜宜大學。

6. 2011/12/20，21 校：中山大學、中央大學、中正大學、中興大學、元智大學、台中教育大學、台北大學、台北市立教育大學、台南大學、交通大學、成功大學、東華大學、虎尾科技大學、逢甲大學、清華大學、嘉義大學、暨南大學、輔仁大學、銘傳大學、澎湖科技大學、靜宜大學。

7. 2012/3/27，25校：大同大學、中山大學、中央大學、中正大學、中華大學、中興大學、元智大學、台中教育大學、台北大學、台北市立教育大學、台南大學、交通大學、成功大學、東華大學、虎尾科技大學、金門大學、屏東教育大學、政治大學、高雄大學、逢甲大學、嘉義大學、實踐大學、輔仁大學、銘傳大學、靜宜大學。

8. 2012/5/29，30校：大同大學、中山大學、中央大學、中華大學、中興大學、元智大學、台中教育大學、台北大學、台北科技大學、台南大學、台灣科技大學、台灣海洋大學、交通大學、成功大學、東華大學、虎尾科技大學、金門大學、屏東教育大學、高雄大學、崑山科技大學、淡江大學、逢甲大學、雲林科技大學、慈濟大學、嘉義大學、實踐大學、輔仁大學、銘傳大學、澎湖科技大學、靜宜大學。

9. 2012/9/25，30校：大同大學、中山大學、中央大學、中正大學、中華大學、中興大學、元智大學、台中教育大學、台北大學、台北市立教育大學、台北科技大學、台南大學、台灣科技大學、台灣海洋大學、交通大學、成功大學、東海大學、東華大學、虎尾科技大學、政治大學、高雄大學、淡江大學、雲林科技大學、嘉義大學、實踐大學、暨南大學、輔仁大學、銘傳大學、靜宜大學、聯合大學。

1.4 CPE計分規則與程式規範

目前CPE的計分規則採取以下兩種方式並行：

• 絕對成績：根據考生答對題數，給予A、B、C、D等級。

• 相對成績：依據ACM-ICPC排名規則，定出考生在該次考試的成績排名。

ACM-ICPC排名計分規則簡述如下：

• 每個題目的結果只有「對」與「錯」，並無部分分數。程式必須答對評判用的所有測試資料，該題才算答對。

• 依照答對題數多寡排定名次。答對題數較多者，排名較前。

• 答對題數相同者，以解題時間總和決定排名。所謂的解題時間總和，係指考試開始至解題正確所經過的時間，再加上罰扣時間（penalty，每送出題解錯誤一次罰加20分鐘）。答錯的題目則不計時間及罰扣時間。

CPE考試時間為3小時，以下提供一個計分範例：假設考試開始時間為18:00，考生甲於18:10答對A題（費時10分鐘），然後於18:25送出B題（但錯誤），18:32答對B題（費時32分鐘，均從考試開始為計時起點），接著於18:50送出C題（但錯誤），則總時間為10＋32＋20×1＝62分鐘（C題未答對，故不計時間）。如果考生乙也同樣答對兩題，而他所花的時間為70分鐘，則考生甲的名次排在考生乙之前。

CPE考試題目的輸出與輸入都不是視窗介面，其程式設計規範如下：

• 考試的程式設計，所有輸入與輸出均採取「標準輸入」(stdin)與「標準輸出」(stdout)，不可使用檔案讀寫。撰寫程式時，於C語言，可使用如scanf與printf函式；於C++，可使用如cin與cout物件。

• 輸入與輸出資料全為純文字資料，必須完全依照題目的輸入與輸出格式撰寫程式。程式要通過評判伺服器的測試資料（不公開），才算「答對」。

• 測試資料的格式必定保證按照題目所給予的輸入與輸出格式，這樣在撰寫程式時，便無需檢查格式是否正確。

• 所撰寫的程式必須有正確的副檔名，如filea.c或filea.cpp等，並且「選擇正確的語言」送繳程式。

送繳程式之後，評審伺服器會回覆一個訊息，只有得到「CORRECT」，該題才算答對。訊息列表參見表1.6。

CHAPTER1程式能力檢定簡介

1.1 ACM國際大學程式競賽

ACM ICPC（International Collegiate Programming Contest，國際大學程式競賽）是由 ACM（Association for Computing Machinery，國際計算機器協會）主辦的一年一次程式設計競賽。藉由競賽方式來展現大學生創新能力、團隊精神，以及在壓力下編寫程式、分析和解決問題的能力。自從1970年代開創以來，經過三十多年的發展，ACM ICPC已成為全球電腦界中歷史最悠久且最具影響力的程式競賽。以2011至2012年為例，參加各地區域賽的隊伍超過8000隊，涵蓋88個國家及超過2000所大學。區域賽優...

拔擢頂尖vs.提升平均

　　由於ACM-ICPC亞洲區黃金雄主任（美國德州大學教授）的鼓勵與協助，「國際計算機器協會程式競賽台灣協會」(ACM ICPC Contest Council for Taiwan) 於2008年成立。成立之初，協會的思考重點都在如何拔擢頂尖，讓更多的頂尖學生參加ACM-ICPC區賽(Regional Contest)及總決賽(World Final)。但我們很快地發現，拔尖只關注大約前5%的少數學生，大部分學生對這些國際競賽幾乎沒有投入甚或注意。根據我們的觀察，由於程式作業抄襲或修改容易，約四分之一的資訊系學生不太會寫程式（各校比率略有差異），四分之三的學生程式寫得不夠多（除了修課作業與專題要求之外不寫程式），未來會選擇從事程式設計的學生不到二分之一，其他傾向轉而投入不太需要撰寫程式的工作。這種「生態」當然影響了國家資通訊產業設計產品的「產能」，而產業界對於大學生的程式設計訓練不夠紮實也是抱怨聲不斷。因為這導致他們在徵聘新人時，必須透過自己設計的程式測驗才能挑選出適合的人才。

　　許多大學教授因有研究論文發表的壓力，對於研究生的研究要求，著重於創新設計與理論分析的突破，而較少要求系統實作之苦工。他們因為專心致力於研究，而無暇顧及基礎的程式教學訓練。有心於大學部程式訓練課程的教授，單憑一己之力也很難改變整個生態。

　　上述的情形讓協會開始在拔尖之餘，開始省思如何提升整體平均。思考的大方向是將ACM-ICPC國際賽的題庫拿來做為標準測驗的題目，然後推廣至各校共同辦理測驗，並且採認於大學部畢業要件與研究所入學參考。因為ACM-ICPC國際賽的題目都經過歷練，有相當的品質與水準，所以不需要擔心題目品質的問題；也因為題庫夠大（目前已經超過3600題，並且陸續增加中），所以也不需要擔心學生可能做過我們所挑選的題目。如果學生做過題目而且在考試時也可以寫得出程式，其程式能力必定也相當不錯，畢竟程式設計需要理解與邏輯思考，無法單靠死背。有了題目品質的保證後，我們設計了「大學程式能力檢定」 (Collegiate Programming Examination, CPE) 做為考試的形式與機制，希望透過CPE及各校的共同參與來改變上述的生態，藉此提高台灣資訊產業的產能與競爭力，並增加參加國際競賽的可能人口。

　　CPE配方：多校、千人、同步、遠距、同一份題目之程式能力檢定

　　CPE具有獨特的配方，而有別於現有的競賽與檢定系統，例如ACM-ICPC區賽與總決賽使用單一實體場地最多100隊同時競賽，或電腦技能檢定在電腦教室隨時有人考試，而考題由遠端的伺服器隨機抽取。上述兩種實體場地或遠端題庫的模式都無法滿足千人同時考試的目標，必須結合兩者才能達到。所以「CPE的配方」是多校、千人、同步、遠距、同一份題目；多校的場地才能免除舟車勞頓，又能達到千人的規模，而遠距題庫能支援各校同步舉辦來考同一份題目。

　　由於CPE是一項檢定考試，監考、防弊與系統穩定度非常重要。學生在各校的電腦教室考試，用戶端的電腦軟體必須確保學生無法連線到非CPE伺服器以外的地方，而CPE係透過虛擬主機的機制達到這項限制。此外，各校考場需避免學生在現場交談作弊，甚或冒名考試，所以電腦教室要有專人監考。伺服器端除了支援多校千人同步存取題目，以及自動評審學生上傳的程式之外，還要克服系統延展性與穩定性的問題。目前CPE系統架構有多台前端與後端伺服器，可兼具支援大量考生及達到伺服器穩定備援的目的。

　　前述提到，題目是由ACM-ICPC區賽與總決賽比賽過而收錄於UVA題庫，品質沒有問題，可以避免多年前資訊教育界推動TGRE因題庫品質問題，造成考試成績鑑別力不足的情形。但是，UVA題庫並沒有公布上傳程式的測試資料（簡稱測資），所以CPE在挑選題目時必須自行準備測資。另外，ACM-ICPC區賽與總決賽進行五小時，三人組成一個隊伍，題目大約在8至10題左右。相較之下，CPE是個人考試檢定，進行三小時，題目有7題，除了時間較短且題目較少外，選擇的題目也朝向簡單化。在一至五顆星難易等級中，ACM-ICPC國際賽一顆星與兩顆星大約各只有一題，其餘題目都是三顆星以上；而CPE一顆星有三題，二顆星有二題，三顆星以上有二題。

　　CPE現況

　　CPE自2010年6月第一次由中山大學與交通大學合辦開始，每季舉辦一次，時間為平日18:00至21:40（包含考前練習）。截至2012年12月已舉辦十次，參與協辦的學校數由2、6、9、19、17、21、25、30校成長到約40校，參加檢定考試的學生數也成長到將近1000人。2011年至2013年由中山大學主辦（選題與測資準備、統籌相關行政事務與對外宣傳），交通大學負責技術支援（伺服器維護），其他學校參與協辦（考場準備與監考）。CPE也提供學生申請中英文成績單，其中會顯示絕對成績（總題數7題、答對題數、成績等級）及相對成績（參加學生數、排名）。由於考試人數夠多、題目具有鑑別力，所以這份成績單具有相當的可信度。程式能力不好的學生，可能一題也解不出來；能解四題的學生，程式能力已是相當優秀；而一次解出兩題是許多大學設定的及格標準。

　　CPE的推行，需要舉辦與採認同時並進，如果沒有學校採認，空有許多學校舉辦，並無法吸引夠多的學生來考試。目前已有多所大學將CPE設定為：(1)大學部之畢業要件（單次考試答對兩題或多次考試累積答對三題或四題）；(2)碩士班甄試入學之參考資料（列入申請表、推薦信或招生簡章）；(3)在課程上使用當作期中期末上機考試的方式。

　　教材設計：系統、基礎、題解

　　儘管有不少線上資源可以讓學生了解ACM-ICPC、UVA、CPE，但仍欠缺一本整合各種資訊的書籍，學生及教師都會需要一本CPE入門的書，讓學生可以準備檢定考試，也讓教師能善加利用CPE於課程、入學與畢業。本教材設計包含三個面向：系統、基礎、題解。在系統方面，我們在第一章介紹ACM-ICPC及CPE的發展與規則；第二章介紹CPE線上(on-line)練習與現場(on-site)考試的系統與機制；第三章介紹一個本機端的練習軟體——瘋狂程設，它透過測資腳本與批改腳本讓學生在練習中減少語法、語意與邏輯的錯誤，也透過短碼競賽讓學生能更精簡地撰寫程式。

　　在基礎方面，第四章介紹C與C++輸入輸出的函式與格式，減少初學者因為程式輸出輸入問題造成上傳程式錯誤的可能；第五章有系統地講解解題技能，從理解題意到挑選合適的演算法（包括排序、搜尋、貪心(greedy)、動態規劃、圖形走訪、最小生成樹、最短路徑、最大流等常用演算法）不一而足，同時考量程式執行時間與記憶體用量，並交代如何設計測資以在上傳程式前檢驗程式的正確性；最後提醒要善用既有資源，利用函式庫來設計解題所需的功能，以減少撰寫程式的時間。

　　在題解方面，我們依據難易等級提供三章共84題之題解，另有8題用在前面章節中做為例子。第六章至第八章分別是一顆星至三顆星題目之題解，除了區分難易度，更依據題型分節，其中包含字元與字串、數學計算、大數運算、幾何、排序、圖論、模擬、動態規劃等。我們希望讀者可以透過本書進入程式設計之門，並培養精進解題與程式的實力。

　　本書特點

　　多校、千人、同步、遠距、同一份考題之大學程式能力檢定(CPE: Collegiate Programming Examination)之入門教材。

　　學生只需具備C或C++基礎程式能力即可上手。

　　線上練習系統與現場考試系統之介紹。

　　基礎輸入輸出與進階解題技能之講解。

　　ACM-ICPC UVA題庫中精選92題題目之題解。

　　依難易度蒐集各類題型：字元與字串、數學計算、大數運算、幾何、排序、圖論、模擬、動態規劃等。

　　每一題解包含UVA/CPE編號、題意、解法、程式碼及程式碼註解。

拔擢頂尖vs.提升平均

　　由於ACM-ICPC亞洲區黃金雄主任（美國德州大學教授）的鼓勵與協助，「國際計算機器協會程式競賽台灣協會」(ACM ICPC Contest Council for Taiwan) 於2008年成立。成立之初，協會的思考重點都在如何拔擢頂尖，讓更多的頂尖學生參加ACM-ICPC區賽(Regional Contest)及總決賽(World Final)。但我們很快地發現，拔尖只關注大約前5%的少數學生，大部分學生對這些國際競賽幾乎沒有投入甚或注意。根據我們的觀察，由於程式作業抄襲或修改容易，約四分之一的資訊系學生不太會寫程式（各校比率略有差異），四分之三的學生程...

第一章 程式能力檢定簡介
第二章 程式能力檢定評審系統
第三章 瘋狂程設軟體
第四章 C/C++基本輸入與輸出
第五章 由基礎至進階
第六章 一顆星題解
第七章 二顆星題解
第八章 三顆星題解

第一章 程式能力檢定簡介
第二章 程式能力檢定評審系統
第三章 瘋狂程設軟體
第四章 C/C++基本輸入與輸出
第五章 由基礎至進階
第六章 一顆星題解
第七章 二顆星題解
第八章 三顆星題解