TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

40.9% (9/22)

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) Output Limit (KiB)
0 2000 524288 65536
1 2000 524288 65536
2 2000 524288 65536
3 2000 524288 65536
4 2000 524288 65536
5 2000 524288 65536
6 2000 524288 65536
7 2000 524288 65536
8 2000 524288 65536
9 2000 524288 65536
10 2000 524288 65536
11 2000 524288 65536
12 2000 524288 65536
13 2000 524288 65536
14 2000 524288 65536
15 2000 524288 65536
16 2000 524288 65536