c458. 7. 片段刪除
Tags :
Accepted rate : 18人/33人 ( 55% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-12-28 18:28

Content

輸入兩個字串,請運用片段刪除的方式,讓這兩個字串變成一樣,規則如下。每次可從
輸入的字串中選取一個長度不超過L的連續片段刪除,請問能否在K次內,完成這項任
務。若是可以,請輸出最少刪除的次數,否則輸出Impossible。
例如L=3、K=2,輸入的兩個字串分別為abcdcbaa 與aaa,則abcdcbaa-->abbaa-->aaa,其
中灰色區塊是欲刪除的字串,所以2次內可以完成任務,且2是最少的操作次數。又如輸入
的字串為abaaabe 與accaaae,L=2、K=3,則abaaabe-->aaaabe-->aaaae,且accaaae-->aaaae,
因此3次內可以完成任務。

Input

每筆測資共有3列,第1列為第1個輸入字串,第2列為第2個輸入字串,輸入字串皆由小寫英文字母組成;第3列共有兩個正整數,分別為L與K,兩者均可存入32位元整數。

Output

針對每筆測資,輸出滿足題意之最少刪除次數,或是Impossible。

Sample Input #1
輸入範例 1:
aaaaa
aaaaaaa
1 2

輸入範例 2:
ababababab
bababababa
2 2

輸入範例 3:
aaaaaaaaaaaaa
bbbbbbbbbbbbb
2 2
Sample Output #1
輸出範例 1:
2

輸出範例 2:
2

輸出範例 3:
Impossible
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (3%): 2.0s , <1K
公開 測資點#1 (2%): 2.0s , <1K
公開 測資點#2 (2%): 2.0s , <1K
公開 測資點#3 (2%): 2.0s , <1K
公開 測資點#4 (2%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (4%): 2.0s , <1K
公開 測資點#8 (4%): 2.0s , <1K
公開 測資點#9 (4%): 2.0s , <1K
公開 測資點#10 (10%): 2.0s , <1M
公開 測資點#11 (10%): 2.0s , <1M
公開 測資點#12 (10%): 2.0s , <1M
公開 測資點#13 (10%): 2.0s , <1M
公開 測資點#14 (9%): 2.0s , <1M
公開 測資點#15 (9%): 2.0s , <1M
公開 測資點#16 (9%): 2.0s , <1M
Hint :

本題共有3個子題,每一子題有多筆測資:
第1子題有5筆測資,兩個輸入字串中僅有字母a,長度均小於130,全解出可得11分;
第2子題有5筆測資,兩個輸入字串長度均小於100,且L=1,全解出可得22分;
第3子題有7筆測資,兩個輸入字串長度均小於10000 個字元;L ≤ 100 且K ≤ 10。全解
出可得67分。

Tags:
出處:
106學年度全國資訊學科能力競賽 [管理者: icube (!@#$%^&*()_...) ]

Status Forum 排行

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