y19m10_a3猴子打字遊戲 (Typing) 2019年10月TOI練習賽 潛力組 {題目連結}
問題敘述
聽過無限猴子定理嗎？此定理說讓一隻猴子在打字機上隨機按鍵，當按鍵數 達到無窮時，幾乎必然能夠打出任何給定的文字。有三個養猴人，他們聽說這個 理論以後，決定辦一個比賽，內容如下： 首先，他們共同決定一段目標文字。然後，每個人各自帶一隻自己養的猴子 坐上打字機，並給予相同時間打字。最後，比賽看誰的猴子打出的文字與目標文 字的最佳編輯距離最小。 編輯距離定義如下：要將字串 y 變成字串 x，可對 y 進行新增、刪除、取 代；其中，新增及刪除一個字元的編輯距離定為 2，取代一個字元的編輯距離定 為 3。舉例來說，將字串 bcde 變成字串 abcc 可以有至少下列兩種不同做法：
上例中，我們稱符號 - 為 gap。第一列有 gap 表示要對第二個字串進行刪除，第 二列有 gap 表示要對第二個字串進行新增；若兩列的字母不同，表示要將第二列 的字串取代為第一列的。以上三種情況都會增加編輯距離，若對應到相同字元則 不會。第一種作法的編輯距離為 7 (2+3+2)，而第二種作法的編輯距離為 11 (2+2+3+2+2)。第一種作法為所有作法中，編輯距離最小的作法，因此將字串 bcde 變成字串 abcc 的最佳編輯距離為 7。
評分說明 此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資 料才能獲得該組分數。L 為字串長度。
第一組 (30 分) : 1<=L<=10。
第二組 (70 分) : 1<=L<=10^4。
每筆測資共四列，每列皆包含一個字串（字串內不包含空格），其長度皆不 大於 L。第一列為給定的目標字串，後三列分別為第一、二、三隻猴子所輸入的 字串。
每組測資輸出兩個數字 N、K，以一個空白隔開。N 為三隻猴子當中，字串 的最佳編輯距離最小的猴子的編號（1、2 或 3），K 為其最佳編輯距離。若有相 同最佳編輯距離，則輸出猴子編號最大的。
abc bcd cde efg
1 4
abcd abcde abc bcd
3 2
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||