TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

58.3% (7/12)

Submission's AC Ratio

22.7% (15/66)

Description

輸入兩個字串,請運用片段刪除的方式,讓這兩個字串變成一樣,規則如下。每次可從輸入的字串中選取一個長度不超過$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 Format

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

Output Format

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

Sample Input

Sample Input #1
aaaaa
aaaaaaa
1 2

Sample Input #2
ababababab
bababababa
2 2

Sample Input #3
aaaaaaaaaaaaa
bbbbbbbbbbbbb
2 2

Sample Output

Sample Output #1
2

Sample Output #2
2

Sample Output #3
Impossible

Hints

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

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第七題

Subtasks

For Testdata: 0 ~ 4, Score: 11
For Testdata: 5 ~ 9, Score: 22
For Testdata: 10 ~ 16, Score: 67
No. Time Limit (ms) Memory Limit (KiB)
0 2000 524288
1 2000 524288
2 2000 524288
3 2000 524288
4 2000 524288
5 2000 524288
6 2000 524288
7 2000 524288
8 2000 524288
9 2000 524288
10 2000 524288
11 2000 524288
12 2000 524288
13 2000 524288
14 2000 524288
15 2000 524288
16 2000 524288