《解题者_黄锦辉》由会员分享，可在线阅读，更多相关《解题者_黄锦辉（16页珍藏版）》请在金锄头文库上搜索。
1、ACM98-1百度文库专用百度文库专用 題組：題組：ACM Programming Contest World Finals, 1998 題號：題號：Problem A：Crystal Clear 解題者：黃錦輝解題者：黃錦輝 解題日期：解題日期：1998 年年 7 月月 28 日日 題意：題意： 可把題意視為在座標圖上，for all ,0,1,2,3, ， 以（，）為圓心，半徑為 1/2 作無數多個圓。在給定一多邊形後，求在此 多邊形內所包函的圓的面積，其中多邊形內所包函的面積計算方式為，若該圓 完全落在多邊形內，則完全計算；若該圓圓心落在多邊形邊上，則只計一半； 若該圓除了圓心以外，有其
2、他部份跟邊相交，則不於計算（若該圓與邊相切， 視為在多邊形內） ；若該圓圓心為多邊形上的一頂點，則面積為此一頂點的內角 （PS: 邊形內角和為（n-） 。 題意範例：題意範例：無（題目上有） 。 解法：解法： 從輸入中先求出 min(x)、max(x)、min(y)、max(y)，for all (x,y)， min(x)表示有兩段小行程1500 50 501000 0 0 解答為第一段飛行高度為 35,000 feet,第二段飛行高度為 30,000 feet,總共耗油 量為 13985 加侖.Sample Input Output for the Sample Input 2(表示有兩個旅
3、程要計算) Flight 1: 35 30 13985 2 Flight 2:20 30 40 23983 1500 50 50 1000 0 0 3 1000 50 0ACM98-32000 0 20 1800 50 100 解法：解法：因需計算飛機在每段小行程之間轉換時爬升或下降而耗費的油量,所以小行 程(leg)之間不獨立, 須利用 dynamic Programming 的方法. 解法範例：解法範例：無 討論：討論：無 程式：程式：無ACM98-4 題組：題組：ACM Programming Contest World Finals, 1998 題號：題號：Problem C: Lea
4、d or Gold 解題者：黃嘉茂解題者：黃嘉茂 解題日期：解題日期：1998 年年 8 月月 25 日日 題意：題意：點石成金，設有 A、B、C 三種元素，今有數種由 A、B、C 組成之混合物，若將這些混合物一某比例合成時，此合成物為黃金。 題意範例：題意範例：現有混合物三種，比例為 1:2:3 、 3:7:1 、2:1:2，現在想做出 3:4:5 比例的合成物。當八份的 1:2:3、一份的 3:7:1、五份的 2:1:2 合成時，恰組成 3:4:5 的合成物，此為其解。 解法：解法：做一矩陣，第一行為 1X+3Y+2Z=3，X、Y、Z 為合成時三種混合物的比例。Ex:1 3 2 3 2 7
5、 1 43 1 2 5 如 X、Y、Z 有正解，這題即為有解。 解法範例：解法範例：Ex: 1 3 2 32 7 1 43 1 2 5 第一行乘 2 減去第二行乘 3 減去第三行- 1 3 2 30 1 -3 -20 -8 -4 -4 第二行乘 8 加上第三行- 1 3 2 30 1 -3 -20 0 -28 -10 檢查第三行是否前三項的正負都和第四項相反，如果是，此題無解，再檢查上一行，如果都有解，此題有解。 討論：討論：上次討論出判斷是否有正解的方法，應推廣到每一行都需做此判斷。 程式：程式：ACM98-5無 題組：題組：ACM Programming Contest World Fin
6、als, 1998 題號：題號：Problem D: Page Selection by Keyword Matching 解題者：史忠榮解題者：史忠榮 解題日期：解題日期：1998 年年 8 月月 28 日日 題意：題意：由關鍵字（Keyword） ，找出最接近的頁 Pages。每頁 Page 最多有個關鍵字。最接近定義如下：假設 Page 1 ： A B CPage 2 ： C DPage 3 ： CA, B, C, D 為關鍵字。查詢（Query）條件為 C A，設一數（本題為） 。則：Page 1 的關聯度為 (8*6)+(7*8) = 104；Page 2 為(8*8)= 64；Pa
7、ge 3 為(8*8) = 64。所以 Output 為：P1 P2 P3。 題意範例：題意範例：參照題意 。 解法：解法：無特殊解法，對每一個 Query，各別求出每頁 Page 的關聯度。 解法範例：解法範例：無。 討論：討論：無。 程式：程式：/*Sample input :P Smalltalk programming computersP computers programmingP computers SmalltalkP FORTRAN programmingP COBOL programmingP programmingQ SmalltalkACM98-6Q programmi
8、ngQ computersQ Smalltalk computersQ Smalltalk programmingQ cooking FrenchESample output :Query PagesQ1 P1 P3Q2 P6 P1 P2 P4 P5Q3 P2 P3 P1Q4 P3 P1 P2Q5 P1 P3 P6 P2 P4Q6*/#include #include #include #define N 8char page25821; / 每頁 Page 的 Keywordsint len25, pagen; / 每頁 Page 的 Keyword 數；全部頁數int compare(co
9、nst void *, const void *);/ 記錄關聯度struct recint index, value;void main()FILE *in;char str300, *ptr;ACM98-7/ 讀入 Page 的 Keywordin = fopen(“page.in“, “r“);for (pagen = 0; ; )fgets(str, 300, in);ptr = strtok(str, “ ntr“);if (strcmp(ptr, “E“) = 0)break;if (strcmp(ptr, “Q“) = 0)continue;for (lenpagen = 0;
10、; lenpagen+)ptr = strtok(NULL, “ ntr“);if (ptr = NULL)break;strcpy(pagepagenlenpagen, ptr);pagen+;fclose(in);/ 讀入 Query 的 Keywordin = fopen(“page.in“, “r“);printf(“Query Pages“);for (int q = 1; ; )char query830;int qlen;fgets(str, 300, in);ACM98-8ptr = strtok(str, “ ntr“);if (strcmp(ptr, “E“) = 0)br
11、eak;if (strcmp(ptr, “P“) = 0)continue;for (qlen = 0; ; qlen+)ptr = strtok(NULL, “ ntr“);if (ptr = NULL)break;strcpy(queryqlen, ptr);rec value25;for (int i = 0; i value value)return 1;/ 假如關聯度一樣，Page 頁碼由小到大if (x - value = y - value)if (x - index y - index)return 1;elsereturn -1;return -1;ACM98-10 題組題組
12、: ACM Programming Contest World Finals, 1998 題號題號: Problem E: Petri Net Simulation 解題者解題者: 張震達張震達 解題日期解題日期: 1998 年年 7 月月 29 日日 題意題意:一個 Petri net 是用來解釋 concurrent activity, 每個 Petri net 的成員有 Places, tokens, transitions, 和路徑 (連通 places 到 transitions 與 連通 transitions 到 places), 而每個 place 可有零個或多個 tokens
13、。本題則是用來模擬 Petri net 之運 作情形。 題意範例題意範例: :如上圖, P1(place)有一個 token, 而 P2 則無任何 token, 此時, T1(transition) 的狀態為 enabled 而 T2 的狀態為 disabled(因為 T1 之輸入 P1 有一 token, 而 T2 之輸入 P2 則無)。又當一 transition 為 enabled, 則它就可以 fire (將 input place 的 tokens removed, 而在 output place 則加入 tokens)。所以, 在上圖, T1 enabled 且 fire 後, 一
14、個 token 由 P1 removed, 而在 P2 則加入一個 token。此時, 我們可知 T1 就變成 disable, 而 T2 則變為 enabled, 所以, 若 T2 此時 fire, 一個 token 由 P2 removed, 而在 P1 處則加入一個 token 。回復到一開始時的情況, 因此很明顯地, 這個 Perti net 會一直重複在這個 cycle 的動作。 解法解法: :以下為解法步驟 : (1) 若輸入的 places 個數為 n, 則宣告一個可放 n 個整數的陣列,用來表示各個 place 所擁有的 token 之個數。 (2) 若輸入的 transiti
15、ons 的個數為 m, 則宣告一個可放 m 個字元的陣列,用來表示 transitions 的狀態 (T 表 enabled, F 表 disabled)。 (3) 再宣告一個 mxn 的二維陣列 (或動態陣列), 用來表示每 transition 的輸入與輸出的 places。(負的代表輸入的 place, 正的則代表輸出的 place) (4) 利用題意所給的各個 place 的輸入輸出的 token 數與路徑數(幾個輸入和 幾個輸出), 來初始化 transitions 之陣列之值。 (5) 依題意給之 fire 數, 去做模擬 Petri net 的動作。(利用 for loop 或 others方法) 解法範例解法範例: : input : 3 (place 數)3 0 0 (各個 place 的 token 數) 3 (transition 數)ACM98-11-1 2 (T1 的 input place 與 output place)-2 -2 3 (T2 的 input place 與 output place)-3
