題目描述

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

1. Each domino completely covers two squares.

2. No two dominoes overlap.

3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

給你一個由 M × N 個正方形組成的矩形板。 此外，您還將獲得無限數量的 2 × 1 方格的標準多米諾骨牌。 您可以旋轉棋子。 要求您在板上放置盡可能多的多米諾骨牌，以滿足以下條件：

1. 每張多米諾骨牌完全覆蓋兩個方格。

2. 沒有兩個多米諾骨牌重疊。

3. 每個多米諾骨牌完全位於棋盤內。 允許觸摸板的邊緣。

找到可以放置在這些限制下的最大多米諾骨牌數量。

輸入格式

In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).

在一行中，給您兩個整數 M 和 N — 棋盤尺寸（1 ≤ M ≤ N ≤ 16）。

輸出格式

Output one number — the maximal number of dominoes, which can be placed.

輸出一個數字 — 可以放置的最大多米諾骨牌數量。

Samples

["2 4\r\n","3 3"]

["4","4"]

原始資料

• Zero1 題號：a776
• Hydro 題號：Z0776
• Locale：zh_TW
• Display：open