課程名稱︰演算法設計方法論
課程性質︰選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資工所
考試日期（年月日）︰2018/12/17
考試時限（分鐘）：3小時
以下包含期中考題和測資，以供學弟妹練習，
每題共有十筆測資，置於文末的Github連結。
試題 :
所有題目均為程試題，語言限制C/C++：
1. Longest Common Subsequence (Dynamic Programming)
Description
一個字串的子序列是由字串中若干個字元(不一定連續)以相同的順序所組成的字串，例如
：AB、ACE、E 都是 ABCDE 的子序列。
兩個字串的最長共同子序列即為兩個字串的共同子序列中字元個數最大者。
Input Format
每組測資包含兩個字串，每個字串長度不超過 100，且全部都是由大寫英文字母組成。
Output Format
第一行請輸出最長共同子序列的長度和個數，下一行開始請依字典順序輸出所有的最長共
同子序列。注意答案中可能包含相同的子序列，因為同一個子序列在兩個輸入字串中的位
置可能不同。保證最長共同子序列的個數不超過 200000 個，LCS長度 >0。
Hint
需要輸出大量的答案，請避免使用緩慢的 I/O 函式。
每筆時限為 1000ms，記憶體上限為 64000KB，保證正確輸出的檔案大小在 32000KB 以內
。
2. 2-Dimensional Linear Programming (Prune & Search)
Description
在二維平面上，使用prune and search技巧，實作線性規劃
Input Format
第一行包含一個正整數 n<=10^5，代表限制條件的個數，
下一行開始每行包含三個整數 -300<=a,b,c<=300，代表 ax+by<=c , 其中 a^2+b^2>0。
Output Format
請輸出滿足所有限制條件的最小 y 值(四捨五入至整數)，若沒有解，請輸出 NA，若為負
無限大，請輸出 -INF。
Hint
需使用 P & S，否則不予計分。
每筆時限為 1000ms，記憶體上限為 64000KB。
3. The 0/1 Knapsack Problem (Branch & Bound)
Description
請使用 branch & bound 策略解決 0/1 背包問題。
Input Format
第一行包含兩個正整數，分別代表背包大小 5 ×10^6，和物品個數<=1000，下一行開始
每行包含兩個正整數，分別代表物品價值 <=10^5，和物品重量 <=10^5。
Output Format
請輸出最大收益。
Hint
請使用 branch & bound 策略，其餘作法(e.g. dynamic programming)不予計分。
4. The 2-Dimensional Closest Pair Problem (Divide & Conquer)
Description
請在二維平面中找出所有最近點對及其距離。
Input Format
每組測資第一行包含一個正整數 2<=n<=2 ×10^5，代表點的個數，接下來 n 行開始每行包
含兩個整數|x|,|y|<=10^9，代表該點的座標，保證所有點的座標皆相異。
Output Format
第一行請輸出兩個數字分別代表最近點對距離的平方以及個數，下一行開始請輸出所有的
配對。每組配對有兩個整數，分別代表兩點輸入時的順序，且第一點為序號較小者。輸出
時請依第一點序號遞增排序，若第一點序號相等，則依第二點序號遞增排序。
Hint
需使用 divide & conquer 策略，而且 time complexity 必須為 O(nlogn+slogs)，其
中 s 為配對數，否則不予記分。
請注意： int 能存取的範圍。
測資下載：
https://bit.ly/2TO26mN