10739 - String to Palindrome

本問題請你轉換一字串使之變成迴文字串(一種從前面寫與從後面寫都一樣的字串，例如abcba)，藉由新增、刪除、取代字母等步驟來轉換成迴文字串，並使轉換的步驟最小化。更精確地說，你可以執行的步驟有三種：

• 新增：插入一字母到字串中任一位置。
• 刪除：刪除字串中任一字母。
• 取代：以一個字母取代字串中任一字母。

每執行上述三種步驟中的任一種即算一次，你必需使轉換步驟愈少愈好。

例如字串"abccda"，如果只允許以新增字母的方式轉換字串，則最少需要兩個步驟，若允許以取代的方式轉換字串，則最少僅需一個步驟。當然，本問題是允許你三種步驟都能使用。

Input

輸入的第一列有一個整數T(1 <= T <= 10)表示接下來有T列測試資料，每列測試資料皆為一個僅含小寫字母的字串，字串長度不會超過1000個字元。

Output

請對每組測試資料輸出其編號，與使字串變成迴文字串的最少步驟為何。

Sample Input                               Output for Sample Input

6 tanbirahmed shahriarmanzoor monirulhasan syedmonowarhossain sadrulhabibchowdhury mohammadsajjadhossain

Case 1: 5 Case 2: 7 Case 3: 6 Case 4: 8 Case 5: 8 Case 6: 8

---

原文出處

10703 - Free spots

The Problem

給定一塊板子，並從中切割出許多矩形區域，請你計算剩下的面積為何。
例如上圖是一塊寬度為6，高度為4的板子，從左下角切出面積為6的小板子，並從上面切出面積為4的小板子，剩下的面積等於14。

The Input

輸入包含多組以空行隔開的測試資料，每組資料的第一列有三個整數W, H, N，分別表示寬度、高度，及切割的小板子數目，其中1 <= W, H<=500，0 <= N <= 99。接下來有N列，每列有四個整數X1, Y1, X2, Y2，(X1, Y1)與(X2, Y2)分別表示矩形小板子的對角座標，其值滿足下列關係：1 <= X1, X2 <= W，且1 <= Y1, Y2 <= H。當W=0, H=0, N=0時表示測試資料結束。上圖的例子可參考下列第四組範例資料。

Output

請參考範例資料輸出每組測試資料的答案。

Sample input

1 1 1
1 1 1 1

2 2 2
1 1 1 2
1 1 2 1

493 182 3
349 148 363 146
241 123 443 147
303 124 293 17

6 4 3
1 1 3 2
2 4 5 4

0 0 0

Sample output

There is no empty spots.
There is one empty spot.
There are 83470 empty spots.
There are 14 empty spots.

---

原文出處