c458: 7. 片段刪除
標籤 :
通過比率 : 80% (4 人 / 5 人 ) (非即時)
評分方式:
Tolerant

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

內容

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

輸入說明

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

輸出說明

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

範例輸入
輸入範例 1:
aaaaa
aaaaaaa
1 2

輸入範例 2:
ababababab
bababababa
2 2

輸入範例 3:
aaaaaaaaaaaaa
bbbbbbbbbbbbb
2 2
範例輸出
輸出範例 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
提示 :

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

標籤:
出處:
106學年度全國資訊學科能力競賽 [編輯:
icube (我都不會)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」