e828: 3.猴子打字遊戲 (Typing)
Tags : DP 最短編輯距離
Accepted rate : 18人/21人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-01-11 00:23

Content

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。

 

Input

每筆測資共四列,每列皆包含一個字串(字串內不包含空格),其長度皆不 大於 L。第一列為給定的目標字串,後三列分別為第一、二、三隻猴子所輸入的 字串。

 

Output

每組測資輸出兩個數字 N、K,以一個空白隔開。N 為三隻猴子當中,字串 的最佳編輯距離最小的猴子的編號(1、2 或 3),K 為其最佳編輯距離。若有相 同最佳編輯距離,則輸出猴子編號最大的。

Sample Input #1
abc
bcd
cde
efg
Sample Output #1
1 4
Sample Input #2
abcd
abcde
abc
bcd
Sample Output #2
3 2
測資資訊:
記憶體限制: 512 MB
公開 測資點#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
Hint :
Tags:
DP 最短編輯距離
出處:
2019年10月TOI練習賽潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」