2040 . 片段刪除

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

tmwilliamlin
我的中文很爛

User's AC Ratio

59.0% (23/39)

Submission's AC Ratio

12.1% (48/398)

Tags

全國賽 2017-全國賽

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 1

aaaaa
aaaaaaa
1 2

Sample Output 1

2

Sample Input 2

ababababab
bababababa
2 2

Sample Output 2

2

Sample Input 3

aaaaaaaaaaaaa
bbbbbbbbbbbbb
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

No. Testdata Range Score
1 0~4 11
2 5~9 22
3 10~16 67

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 262144 1
1 2000 524288 262144 1
2 2000 524288 262144 1
3 2000 524288 262144 1
4 2000 524288 262144 1
5 2000 524288 262144 2
6 2000 524288 262144 2
7 2000 524288 262144 2
8 2000 524288 262144 2
9 2000 524288 262144 2
10 2000 524288 262144 3
11 2000 524288 262144 3
12 2000 524288 262144 3
13 2000 524288 262144 3
14 2000 524288 262144 3
15 2000 524288 262144 3
16 2000 524288 262144 3
Submit
Back to Top