c458. 7. 片段刪除 - 高中生程式解題系統

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 (!@#$%^&*()_...) ]

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