CF50A Domino piling

给定一个 $M \times N$ 的矩形棋盘。你还拥有无限数量的标准多米诺骨牌，每个多米诺骨牌可以覆盖 $2 \times 1$ 的格子。你可以旋转这些多米诺骨牌。请你在如下条件下尽可能多地在棋盘上放置多米诺骨牌： 1. 每个多米诺骨牌完全覆盖两个格子。 2. 任何两个多米诺骨牌不能重叠。 3. 每个多米诺骨牌必须完全放在棋盘内，可以接触棋盘的边缘。 请你求出在这些限制下，可以放置的多米诺骨牌的最大数量。

输入仅一行，包含两个整数 $M$ 和 $N$，表示棋盘的大小（$1\leq M\leq N\leq16$）。

输出一个整数，表示最多可以放置多少个多米诺骨牌。

由 ChatGPT 5 翻译