1422 . 小米雷射 (Laser)
TopCoder
Description
為了防止盜畫，美術館找來了小雷保全公司為他們設計安全系統，以偵測並防止竊賊的進入。因此小雷保全決定在美術館的展間裏安置小米雷射裝置來保護展出的名畫。小米雷射有別於一般的雷射，它可以發出米字型的雷射光，也就是小米雷射所在的那一行、那一列，以及兩條對角線上的空間都能被雷射光掃描到。然而小米雷射的雷射光具有破壞力，在電射光所能及的路線上不能擺放其他小米雷射，否則會被雷射光燒壞。如下圖(a)所示，在座標 $(2,3)$ 放一個小米雷射，則灰底的區域都可被成功的保護。由於小米雷射非常昂貴，小雷保全為了降低成本，必須要設法在每一個不同形狀大小的展間放置最少的小米雷射來確保能完整掃描展間的所有空間。例如，下圖(b)中為一個$ 3\times 4$ 的展間，若在此展間的$ (2,3)$及$ (1,1)$ 兩個座標位置各放一個小米雷射，就能完整掃描整個展間，且所有小米雷射都不會被其他小米雷射的電射光破壞，因此此一 $3\times 4 $的展間，只需要兩個小米雷射就能達到完全的安全防護。請寫一個程式計算能完整掃描整個展間所需最少小米雷射數量。
Input Format
輸入只有一列，有兩個整數$m$及$n$，以空白字元隔開，代表一個長為$m$個單位，寬為$n$個單位的展間。對於所有的測試資料，保證$1 \leq n, m \leq 100$。
Output Format
請根據輸入資料，輸出能完整掃描該展間所需最少小米雷射數量。
Sample Input 1
3 4
Sample Output 1
2
Sample Input 2
5 5
Sample Output 2
3
Hints
Problem Source
臺北市105學年度高級中學資訊學科能力競賽程式設計試題第四題
Set by Yihda Yol
若測資有誤請儘快聯絡管管(?
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $1 \leq n, m \leq 6$ | 20 |
| 2 | 5~9 | $1 \leq n, m \leq 9$ | 30 |
| 3 | 0~16 | $nm \leq 120$ | 50 |