← 返回题目列表

Codeforces · 111/C

C. 彼佳和蜘蛛

中文机器翻译题面 查看原题

小彼佳喜欢训练蜘蛛。 Petya 有一块大小为 n × m 的棋盘。棋盘的每个单元格上最初都有一只蜘蛛。一秒钟后,彼佳为每只蜘蛛选择特定的动作,然后所有蜘蛛都会谦卑地执行命令。有 5 种可能的命令:保持空闲或从当前单元格移动到四个侧面相邻单元格中的一些单元格(即,四个可能方向中的每一个方向都有一个命令)。佩蒂亚发出命令,这样蜘蛛就不会离开场地。当蜘蛛以相反的方向向彼此爬行时,允许它们相互穿过。所有蜘蛛同时爬行,并且几只蜘蛛最终可能会出现在一个牢房中。 Petya 想知道一秒钟后无蜘蛛细胞的最大可能数量。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 40, n·m ≤ 40) — 棋盘尺寸。

输出

在第一行打印没有蜘蛛的最大单元格数。

示例

输入 #1

1 1

输出 #1

0

输入 #2

2 3

输出 #2

4

注意

在第一个示例中,唯一可能的答案是:

s

在第二个示例中,可能的解决方案之一是:

s 表示命令“保持空闲”,l、r、d、u 分别表示命令“向左爬行”、“向右爬行”、“向下爬行”、“向上爬行”。