TopCoder

Thumb %e6%88%aa%e5%9c%96 2020 01 16 %e4%b8%8b%e5%8d%884.18.54
8e7
呃 我弱

User's AC Ratio

86.5% (32/37)

Submission's AC Ratio

30.6% (52/170)

Description

  芳佳最近在資料整理室打工,她被分派去檢查明娜中校準備要提交到總部那裡的文件有沒有錯誤。

  沒想到芳佳一打開Word檔,發現裡頭錯誤一大堆,要改起來還挺麻煩的,而且改太久還會影響到訓練的時間,於是她決定以最快的速度完成這工作。

  芳佳能做的動作有幾種:

   1.在原始文章中增加一個字元

   2.從原始文章中刪除一個字元

   3.把原始文章中的一個字元替換成另外一個字元

  芳佳最少要花多少動作才能結束這工作呢?

Input Format

本題只有一筆測試資料

第一行是原本有錯的文章

第二行則是正確的文章

兩行都不會超過1000個字元

Output Format

請輸出一個數字k代表最少需要多少動作才能從錯誤的文章改成正確的

Sample Input

hallogameboy
hgameboy

Sample Output

4

Hints

Problem Source

原TIOJ1385 / 快樂暑假營第三次練習比賽。
Problem Setter:hallogameboy

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8