問題 1 - 地震源與觀測站的距離計算 [1] (5 分 ) 問題描述地震時會同時產生 P 波與 S 波, P 波是縱波其波速約 N1 ( 公里 / 秒 )km/s, S 波是橫波其波速約為 ( 公里 / 秒 ) N2 km/s 一觀測站在某次大地震中測得 P 波抵達後的 N3 秒 S 波也抵達, 若這兩種波沿著同一直線路徑由震源傳到觀測站, 則我們需要一程式計算震源與觀測站的距離為多少公里 (km) 輸入格式 N1 N2 N3 為正整數 輸出格式正整數, 或是, None: 如果計算出來的距離為負, 不為正整數則輸出英文字 None 資料範圍 1<= N1 <= 12 正整數 1<= N2 <= 8 正整數 1<= N3 <= 10000 正整數 資料範例輸入範例 1 9 5 12 輸出範例 1 135 輸入範例 2 10 5 10 輸出範例 2 100 輸入範例 3 5 10 10 輸出範例 3 None 1
範例解釋輸入範例 3, N1=5, N2=10, N3=10 距離算出為負, 所以輸出為 None 參考資料 : 1. 本題目部份內容部份引用 105 物理指考 2
問題 5 - 大家來數羊 (10 分 ) 問題描述一群失眠的朋友組成互助會, 大家一起數羊入睡 數羊的方法為, 每個人由左到右排列編號, 由第一個人從 1 開始數, 每數一個數字, 就加一並從右邊醒著的第一個人接著數, 如果右邊沒有人, 則從頭從左邊第一個醒著的人開始數 每個人都有自己喜好的數字, 當數到此數字的倍數時就會睡著, 不過數羊本身的人不會睡著 現在給定每個人的喜好數字, 請問最後一個還醒著的人是第幾位? 輸入格式 N S_1 S_2... S_N 共有 N+1 個數字, 第一個數字表示有幾個人, 接著 N 個數字表示每個人的喜好數字 編號從 1 開始到 N 輸出格式 X X 是正整數, 表示最後一個醒著的人 資料範圍 1 <= N <= 100 1 <= i <= N 1 <= S_i <= 1000 資料範例輸入範例 1 2 1 1 輸出範例 1 1 輸入範例 2 3 2 4 4 輸出範例 2 2 輸入範例 3 3
5 5 4 3 2 1 輸出範例 3 3 範例解釋範例 1, 一共有 2 個人, 第 1 人數 1 的時候, 第 2 人睡著 最後醒著的是第 1 個人 範例 2, 一共有三個人, 第 2 人數到 2 的時候, 第 1 人睡著, 第 2 人再數到 4 的時候, 第 3 人睡著 最後醒著的是第 2 個人 4
問題 6 - 窮舉法練習 (10 分 ) 前言在演算法中," 窮舉所有的可能 " 是基本本領 ( 通常會再從其中找更快效率的方法, 但本題並無沒有捷徑 - 因為就是要所有答案 ), 是一個演算法基礎練習 問題描述請寫一程式, 輸入一個正整數 N, 前 N 個大寫字母每個字母使用一次, 可以組成哪些字串? 請將所有排列依字碼順序, 從小到大列出來, 每行印出一種排列. 字串的字碼順序大小, 指的兩字串間, 第一個不同的字母比較大小. 例如 DABC 與 DACB, 前面 DA 都相同, 第一個不同字母分別是 B 與 C, B 比 C 小, 所以 DABC 比 DACB 小, 故 DABC 應列在 DACB 之前. 輸入格式 N 輸出格式前 N 個大寫字母每個字母使用一次, 可以組成的所有字串 依字碼順序, 從小到大列出來, 每行印出一種排列 資料範圍 1 < N <= 10 資料範例輸入範例 1 3 輸出範例 1 ABC ACB BAC BCA CAB CBA 5
輸入範例 2 2 輸出範例 2 AB BA 輸入範例 3 4 輸出範例 3 ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA 範例解釋範例 2 的輸入 2, 則所有表示 "A" 和 "B 的字串組合依序輸出第一行為 AB, 以及第二行為 BA 6
問題 7 - 細菌繁殖數量第一題 (10 分 ) 問題描述少年圖靈正在做生物實驗, 發現物種的繁殖會有一種規律性, 可以來計算細菌的數量 細菌繁殖的特徵如下 : 在一小時後, 會有一半的細菌死亡, 一半的細菌存活 細菌最多活滿 3 小時 所以我們把細菌生存分為三級別,A 級別細菌表示剛分裂且未滿 1 小時的細菌,B 級別細菌表示分裂滿 1 小時且未滿 2 小時的細菌,C 級別細菌表示分裂滿 2 小時且未滿 3 小時的細菌 細菌的分裂方式為 :A 級細菌不具備分裂能力 B 級細菌才開始分裂, 且平均每隻細菌可分裂出 6 隻新細菌 C 級細菌則平均每隻細菌可分裂出 8 隻新細菌 我們把不同級數的數量輸入成為第一小時的數量, 想求得一小時後不同級別的細菌量 輸入格式輸入數據為 3 個用空格分開的整數, 依序為 A 級別細菌的數量,B 級別細菌的數量, 與 C 級別細菌的數量 輸出格式輸出一行數據答案, 數據為 3 個用空格分開的整數, 依序為 A 級別細菌的數量,B 級別細菌的數量, 與 C 級別細菌的數量 資料範圍輸入之每個數值為偶數, 或 0, 範圍在 0 到 998 之間 資料範例輸入範例 1 10 2 0 輸出範例 1 12 5 1 輸入範例 2 10 4 2 輸出範例 2 40 5 2 輸入範例 3 400 200 100 7
輸出範例 3 2000 200 100 範例解釋範例解釋 1 A 10 B 2 C 0 第一小時 A 級別 10 隻細菌隔一小時後成為 5 隻 B 級別細菌 B 級別細菌隔在這一小時中, 分裂出 12 隻 A 級別細菌, 且最後成為 1 隻 C 級別細菌 累算後, 得到 12 隻 A 級別細菌,5 隻 B 級別細菌, 1 隻 C 級別細菌 8
問題 8 - 細菌繁殖數量第二題 (10 分 ) 問題描述延續上一題, 少年圖靈發現, 若經過 N 小時的繁殖, 不同級別的細菌總量比例會成為穩定分配 那如果細菌分裂的的數量不同, 則某種分裂方式最後的穩定分配為何? 輸入格式輸入數據為 3 個用空格分開的整數, 依序為 A 級別細菌的能分裂的數量,B 級別細菌能分裂的數量, 與 C 級別細菌能分裂的數量 輸出格式輸出一行數據答案, 數據為 3 個用空格分開的整數, 依序為 A 級別細菌對 C 級別細菌的比例, B 級別細菌對 C 級別細菌的比例, 與 C 級別細菌的基數 (1) 資料範圍輸入之每個數值範圍在 0 到 50 之間 輸出數值為正整數 資料範例輸入範例 1 0 6 8 輸出範例 1 16 4 1 輸入範例 2 0 12 36 輸出範例 2 36 6 1 輸入範例 3 1 4 48 輸出範例 3 36 6 1 9
範例解釋範例 1 A 級別細菌不分裂,B 級別細菌分類 6 隻新細菌,C 級別細菌分裂 8 隻新細菌 若干小時後, 三種細菌數量的比例會成為 16:4:1, 答案為 16 4 1 10
問題 11 - 珠算加法 (15 分 ) 前言珠算最早在西元前 2300 年前在美索不達米亞平原就被發現已在使用, 它橫跨幾個世界早前文明流傳至今, 並且沒有太大的變動, 其有限狀態機 (finite state machine) 的內含原理在當今電腦暫存器或是作業系統中都能看到 ~ 狀態的更動, 值的變動更是 programming 的精髓 ~ 隨著 3C 產品,Google 與建構式數學的大量使用, 珠算這種古人千年智慧的結晶正在消失和沒落, 需要你協助傳承 推陳出新和發揚 問題描述基本的珠算算盤有 23 柱, 假設以第 12 柱為小數點, 則小數有 11 位, 上面的算珠代表 5, 下面則有 4 個算珠, 做加法時基本是利用口訣並產生各柱狀態的改變, 而非數學運算 我們要設計一個珠算的輔助工具, 透過 Text to Speech (TTS) 轉為語言教小朋友如何操作算盤, 而現在的問題便是如何先將運算產生口訣 假設英文字母 C 表示 去, 而 J 表示 進 而加數 1~9, 遇到 不進五, 或 進五, 或 進十, 或 去五進十 的各種狀態的基本口訣可表示為下表 : 加數不進五進五進十去五進十 1 進一 (J1) 去四進五 (C4J5) 2 進二 (J2) 去三進五 (C3J5) 3 進三 (J3) 去二進五 (C2J5) 4 進四 (J4) 去一進五 (C1J5) 去九進十 (C9J10) 去八進十 (C8J10) 去七進十 (C7J10) 去六進十 (C6J10) 11
5 進五 (J5) 去五進十 (C5J10) 6 進六 (J6) 去四進十 (C4J10) 7 進七 (J7) 去三進十 (C3J10) 8 進八 (J8) 去二進十 (C2J10) 9 進九 (J9) 去一進十 (C1J10) 去五進十進一 (C5J10J1) 去五進十進二 (C5J10J2) 去五進十進三 (C5J10J3) 去五進十進四 (C5J10J4) 舉輸入範例 1 的例子說明, 23.45 + 567.8 的作法如下 : 被加數 23.45 為已知, 是既有的狀態 加數 567.8 是需要透過口訣 ( 也就這例子的答案 ), 去操作改變算盤中各柱及珠之狀態 小數點位數要先對好 珠算的加法是由左到右, 所以, 需要產生的口訣便是 : J5J6C3J10J1C2J10J1 如果你還看不懂請繼續看範例解釋 2 輸入格式輸入兩個數字 : 被加數, 加數, 中間隔以空白 輸出格式輸出口訣 資料範圍 0 999999999.99999999 資料範例輸入範例 1 23.45 567.8 輸出範例 1 J5J6C3J10J1C2J10J1 輸入範例 2 37.2121 967.8409 12
輸出範例 2 J9J6C5J2J10C9J10C9J10J1C2J10C4J5C1J5C1J10J1 範例解釋 2 9 => J9 ( 進 9) 6 => J6 ( 進 6) 7=> C5J2J10C9J10C9J10J1 ( 遇到進十, 操作可細分為以下數動 ) 去 5 進 2 進 10, ( 因為遇到進十, 要操作左邊柱珠加 1 的狀態 ) 去 9 進 10, ( 加 1 後, 又遇到進十, 要操作左邊柱珠加 1 的狀態 ) 去 9 進 10, ( 加 1 後, 又遇到進十, 要操作左邊柱珠加 1 的狀態 ) 進 1, ( 因為沒遇到進十或進五, 所以操作左邊柱珠直接進 1) 8 => C2J10C4J5 ( 去 2 進 10, 去 4 進 5) 4 => C1J5 ( 去 1 進 5) 0 => ( 珠子不動, 不用產生口訣 ) 9 => C1J10J1 ( 去 1 進 10 進 1) 13
問題 12 - 編輯距離 (Hamming Distance) (15 分 ) 前言在人工智慧的領域中, 模糊的快速比對是極常見的運算. 因此常需要計算兩個字串間的相似或相異度. 編輯距離是用來表示字串間相異度的一種方法 ( 編輯距離指的是經過多少操作後可以把兩個字串變成一樣 ). 問題描述 請依下列定義製作一個程式來計算將第一個字串轉換成第二個字串兩字串的編輯距離 : 若兩個字串 A 與 B, 最少需要 X 的編輯代價, 才能把 A 完全變成 B, 則稱 A 字串到 B 字串的編輯 距離為 X. 可進行的編輯動作有下列三種, 每做一次都要付出相對的編輯代價 : 編輯動作編輯代價說明 刪除 3 刪除一個位置上的一個字元 插入 4 在某一位置插入任一個字元 取代 5 將某一位置的字元取代成任一個字元 輸入格式第一個字串第二個字串 輸出格式 X X = 正整數, 編輯距離 資料範圍輸入資料可為任何可由鍵盤輸入的字串, 含英文, 數字, 以及常用符號 資料範例輸入範例 1 ABCDEFK BCGDHK 輸出範例 1 14
15 輸入範例 2 There is no good player. Who say the player is not good? 輸出範例 2 92 範例解釋範例 1 的輸出 15, 表示 "ABCDEFK" 到 "BCGDHK" 的編輯距離為 15, 因為最少需要編輯代價 15( 刪除 x2, 插入 x1, 取代 x1). 將 "ABCDEFK" 編輯成 "BCGDHK") 最佳編輯過程有好幾種, 下面是其中一個例子 : 原始字串 : "ABCDEFK" 編輯動作 1 : 將位置 0( 此時為 'A') 的字元刪除 ==> "BCDEFK" 3 編輯動作 2 : 在位置 1( 此時為 'C') 之後插入 'G' ==> "BCGDEFK" 4 + 3 = 7 編輯動作 3 : 將位置 4( 此時為 'E') 取代成 'H' ==> "BCGDHFK" 5 + 7 = 12 編輯動作 4 : 將位置 5( 此時為 'F') 的字元刪除 ==> "BCGDHK" 3 + 12 = 15 範例 2 則可以用 3 次取代,7 次刪除,14 次插入將 "There is no good player." 轉換成 "Who say the player is not good?", 因此編輯距離是 3x5+7x3+14x4 = 92. 沒有更小的, 所以輸出 92 15
問題 14 最快路徑 (15 分 ) 問題描述小靈和朋友要開車到附近的城市遊玩 他們從城市 1 出發, 目的地為城市 N 某些城市之間有公路連接, 並且已知每條公路所需的路程, 請你幫他們找出總車程最快要多少小時? 輸入格式 N M A1 B1 T1 A2 B2 T2 AM BM TM 以上皆為正整數 輸出格式 X X 表示從城市 1 到城市 N 最快需要多少小時, 如果城市 1 無法到達城市 N, 輸出 -1 資料範圍 1<=N<=10 N 為正整數, 表示城市的數目 1<=M<=100 M 為正整數, 表示公路的數目 Ai Bi Ti 表示城市 Ai 和城市 Bi 之間有一條公路, 車程為 Ti 小時, 而且兩個城市之間連接的公路至多只有一條 資料範例輸入範例 1 3 2 1 2 5 2 3 6 輸出範例 1 11 輸入範例 2 10 1 1 2 1 16
輸出範例 2-1 輸入範例 3 4 5 1 2 5 1 3 8 2 3 3 3 4 1 4 1 10 輸出範例 3 9 範例資料 3 的圖示 : 範例解釋範例 1 中, 3 個城市之間有 2 條道路, 城市 1 到城市 2 要 5 小時 城市 2 到城市 3 要 6 小時, 則城市 1 到城市 3 最快 11 小時可到達 範例 2 中, 10 個城市之間只有 1 條路, 城市 1 到城市 10 之間沒有道路, 故輸出為 -1 範例 3 中, 城市 1 到城市 4 之間有 5 道路, 且最快 9 小時可到達 17
問題 15 總路程限定下之最快路徑 (20 分 ) 問題描述小靈和朋友又要開車到附近的城市遊玩, 不過這次他們為了控制預算, 所以將路程限定在 L 公里以內 他們從城市 1 出發, 目的地為城市 N 某些城市之間有公路連接, 並且已知每條公路的長度, 以及所需的車程 請你幫他們找出在 L 公里總路程限定條件下, 總車程最快要多少小時? 輸入格式 N M L A1 B1 T1 L1 A2 B2 T2 L2 AM BM TM LM 輸出格式 X X 表示從城市 1 到城市 N 最快需要多少小時, 如果城市 1 無法到達城市 N, 輸出 -1 資料範圍 1<=N<=12 N 為正整數, 表示城市的數目 1<=M<=100 M 為正整數, 表示公路的數目 1<=L<=100 L 為正整數, 表示該次旅行最多可以行駛的距離 ( 總公里數 ) Ai Bi Ti Li 表示城市 Ai 和城市 Bi 之間有一條公路, 車程為 Ti 小時, 距離為 Li 公里, 而且兩個城市之間連接的公路至多只有一條 1<=Ti<=100 T 為正整數, 表示公路的車程 ( 時數 ) 1<=Li<=100 L 為正整數, 表示公路的長度 ( 公里數 ) 資料範例輸入範例 1 3 3 2 1 2 4 1 1 3 5 5 2 3 6 1 輸出範例 1 10 18
輸入範例 2 5 5 9 1 2 1 1 2 3 1 1 3 4 1 1 4 5 1 1 1 5 3 10 輸出範例 2 4 輸入範例 3 6 3 7 1 3 5 1 2 4 6 2 3 5 2 3 輸出範例 3-1 範例解釋範例 1, 第 1 行 3 3 2 表示 3 個城市之間有 3 條道路, 但該次旅行最多可以行駛的距離不得超過 2 公里 第 3 行 1 3 5 5 表示城市 1 到 3 有條道路, 車程是 5 小時, 距離 5 公里 但因該次旅行最多可以行駛的距離不得超過 2 公里, 故該路不可行 因此, 最快的路徑是城市 1 --> 城市 2 --> 城市 3, 車程共需 10 小時 19
問題 16 - 同餘除法 (20 分 ) 前言密碼學 ( 數位簽章及安全通信如 SSL 的基礎 ) 中, 同餘計算是極常見的. 簡單說明如下 : 對任一個正整數 N, 如果整數 A 除以 N 餘數為 B(B 必在 0..N-1 範圍內 ), 則稱 A 與 B 在數域 N 中同餘, 記作 A = B (Mod N) 以 N 為 13 時為例, 27 = 1 (Mod 13) 因 27 % 13 = 1 64 = 12 (Mod 13) 因 64 % 13 = 12-16 = 10 (Mod 13) 因 -16 % 13 = 10, 結果都取 0..N-1 間, -16 = (-2)*13 + 10 在此定義下, 數域 N 中的同餘加法, 減法, 乘法都可以用標準的的加, 減, 乘法運算, 然後求除以 N 的餘數就好了 10 + 8 = 18 = 5 (Mod 13) ==> (10+8)%13 = 5 5-8 = -3 = 10 (Mod 13) ==> ( 5-8)%13 = 10 11 * 7 = 77 = 12 (Mod 13) ==> (11*7)%13 = 12 這可以看出同餘計算時, 減法是加法的逆運算, 就是說 : 10 + 8 = 5 (Mod 13) => 5-8 = 10 (Mod 13) => 5-10 = 8 (Mod 13) 用同樣道理同餘計算時, 除法是乘法的逆運算 : 11 * 7 = 12 (Mod 13) => 12 / 7 = 11 (Mod 13) => 12 / 11 = 7 (Mod 13) 這就是所謂的同餘除法, 簡單的說數域 N 中, A 除以 B, 就是在 0 到 N-1 中找一個 Q 使得 (B*Q)%N 等於 A, 這個 Q 就是 A/B 的結果 問題描述請寫一個計算同餘除法的程式, 分別輸入被除數 A, 除數 B, 以及數域 N, 輸出在數域 N 中 A 除以 B 的結果. 輸入格式 A B N 20
輸出格式 Q Q = 數域 N 中 A 除以 B 的結果無解時 ( 如範例 2) 請輸出 -1 符合的答案不只一個時 ( 如範例 3), 輸出最小的那個答案. 資料範圍 N 必為 150 位以內之正整數, 而 A, B 都會在 [0..N-1] 的區間 A, B, N 可能很大 ( 長整數 ), 用迴圈試乘方式固然可解得答案, 但效率極差, 很可能無法在限制時間跑出結果. 資料範例輸入範例 1 12 11 13 輸出範例 1 7 輸入範例 2 5 12 22 輸出範例 2-1 輸入範例 3 4 6 10 輸出範例 3 4 輸入範例 4 733331234 1231251113 2147483647 輸出範例 4 288819309 21
輸入範例 5 1111111111111111111111111111111111111111111111111111111111111111111111111 9876543210123456789876543210123456789876543210123456789876543210123456789 115792089237316195423570985008687907853269984665640564039457584007913129639471 輸出範例 5 37773418830809571037385147999308115039457043813565765348601628832345755603929 範例解釋 [ 範例 1]: 11 乘以 ( 7 ) 後, 除以 13 的餘數會得到 12, 所以 12/11= 7 (Mod 13), 輸出 7 [ 範例 2]: 12 不論乘甚麼整數, 除以 22 的餘數必然是偶數, 不可能是 5, 所以 5/12 (Mod 22) 無解, 輸出 -1 [ 範例 3]: 6 乘以 ( 4 ) 或 ( 9 ) 以後, 除以 10 的餘數都是 4, 所以 4/6 (Mod 10) = Minimum (4, 9) = 4 22
問題 17 - 多元一次聯立方程式 (25 分 ) 問題敍述大家數學課都做過多元一次聯立方程式求解. 下列的二元一次聯立方程式, 相信大家都解得出來 X=1, Y=1. 3 * X + 2 * Y = 5 2 * X - 5 * Y = -3 但是如果變數多 ( 例如 5 個變數甚至更多 ), 解的時候就麻煩多了 請寫一支程式求解下列 N 元一次聯立方程式, C11*X1 + C12*X2 + + C1N*XN = O1 C21*X1 + C22*X2 + + C2N*XN = O2. 輸入格式 N CN1*X1 + CN2*X2 + + CNN*XN = ON C11 C12 C1N O1 C21 C22 C2N O2. CN1 CN2 CNN ON 輸入第一行正整數 N, 代表方程式有 N 個變數, 以及後續會有 N 個方程式 第二行起, 共會有 N 行輸入, 每一行代表一組方程式, 有 N+1 個正整數, 以空白分隔 Cn1 Cn2 CnN 代表第 n 條方程式的 N 個乘法係數, On 為方程式等號右側常數. (n=1~n) 輸出格式 X1 X2 XN 或是 當聯立方程式有唯一解時, 以最簡有理數格式輸出變數 (X1 XN) 的解 NA 當聯立方程式無解時, 輸出字串 NA 或是 INF 當聯立方程式有無限多解, 輸出字串 INF 當聯立方程式有唯一解時, 輸出格式應注意 : 1. 因本題輸入係數全為整數, 有唯一解時, 其解必全為有理數, 2. 應以最簡有理數以空白分隔輸出, 3. 最簡有理數輸出格式定義如下 : i. 整數直接輸出, 非整數以分數表示. 正數一律不顯示正號 (+). ii. 分數的表示法為 A/B, 當中 A 必為整數, 而 B 必為正整數, 而且 A 與 B 無法再約分 例如, 23
2/7-5 -28/13 0 這幾個表示法都是正確的 24/15 5/1 33/-7 +5 這幾個表示法都是錯誤的, 分別應改成 8/5 5-33/7 5 本題要答精確值, 不接受近似小數 ( 例如, 4/3 不可輸出成 1.3333) 資料範圍 1 <= N <= 5 變數個數 N: 小於或等於 5 的正整數 -7 <= Cmn <= 7(m,n=1~N) 方程式係數 : 介於正負 7 間的整數 -8 <= On <= 8 (n=1~n) 方程式等號右側常數 : 介於正負 8 間的整數 資料範例輸入範例 1 2 3 2 5 2-5 -3 輸出範例 1 1 1 輸入範例 2 4 2 3 0-3 -1-1 -1-3 3-2 0-2 2-1 0 1 1 1 1 1 輸出範例 2-3/2 1 7/6 1/3 輸入範例 3 2 1 1 2 2 2 4 輸出範例 3 INF 輸入範例 4 3 1 2 3 5 3 1 2 4 2 4 6 8 輸出範例 4 NA 24
範例解釋範例輸入 1, 第 1 行 : 2, 代表 2 個變數, 2 個方程式第 2 行 : 3 2 5 代表 3*X1 + 2*X2 = 5, 第 3 行 : 2-5 -3 代表 2*X1 + (-5)*X2 = -3 範例輸出 1, 1 1 代表 2 個變數的答案為 X1=1, X2=1 25