#P15833. [蓝桥杯第一届国际赛] 仓库布局

[蓝桥杯第一届国际赛] 仓库布局

说明

小明管理着一个仓库,他要在仓库里面摆放一些货柜。货柜比较高,不能上下堆叠,底面是正方形,有一个侧面为正面,用于取放货物。

小明将仓库划分成了 n×mn \times m 的方格,其中南北方向 nn 格,东西方向 mm 格。每个方格可能放置一个货柜,也可能作为过道。为了使仓库整齐有条理,小明的货柜的正面都朝南或朝北。具体的,从北向南第一行货柜朝南,第二行全部为过道,第三行货柜朝北,第四行货柜朝南,第五行全部为过道,第六行货柜朝北,第七行货柜朝南,第八行全部为过道,依次类推。如果第 nn 行为朝南的货柜,则由于无法取放货柜中的货物,只能将这排货柜撤除,此时第 nn 行改为过道。

小明不仅有东西方向的过道,还有南北方向的过道,他每隔连续的 55 格都分出了一个南北方向的过道,即从西向东第 6612121818 列都是过道。

依照以上规则,当 n=6n = 6m=8m = 8 时,仓库的摆放图如下:

【缺图】

n=4n = 4m=8m = 8 时,仓库的摆放图如下,虚线框中是被撤除的货柜:

【缺图】

给定 n,mn, m,请问按照小明的货柜摆放规则,仓库中可以放置多少个货柜(不计算被撤除的货柜)。

输入格式

输入一行包含两个整数 n,mn, m

输出格式

输出一个整数,表示可以摆放的货柜数量。

6 8
28

提示

评测用例规模与约定

对于 30% 的评测用例,1n100,6m1001 \le n \le 100, 6 \le m \le 100

对于 70% 的评测用例,1n10000,6m100001 \le n \le 10000, 6 \le m \le 10000

对于所有评测用例,1n109,6m1091 \le n \le 10^9, 6 \le m \le 10^9