#52. 切蛋糕

切蛋糕

【题目描述】

小明买了一块 n×mn × m 的蛋糕,他打算分给三个人吃,为了美观,小明只会在整数的 位置切蛋糕,而且会一切到底,也就是说如果他在蛋糕上切了一刀,起点和终点一定都在 边界上,同时为了方便,他的痕迹一定是平行于某条边界的线段。很容易看出,小明的切 法一定会把蛋糕切成三个长方形。另外要注意,当小明切了一刀后,蛋糕自动一分为二, 会产生新的边界,下一刀的起点或终点可以产生在新的边界上。现在小明希望三个人拿 到的蛋糕尽量的平均,也就是三个人当中,分到的最大面积和最小面积之差最小,他先 知道这个最小值是多少。

【输入格式】

从文件 cake.incake.in 中读入数据。

一行两个整数 n,mn, m

【输出格式】 输出到文件 cake.outcake.out 中。

只有一行,表示最大面积与最小面积之差。

【样例 1 输入】

3 3

【样例 1 输出】

0

【样例 1 解释】

很显然平行或垂直按间隔为 1 切两刀,可以把蛋糕分成三等分。

【数据范围】

数据约束和子任务

对于 30% 的数据,n,m10n, m ≤ 10

对于 70% 的数据,n,m3000n, m ≤ 3000

对于 100% 的数据,n,m105n, m ≤ 10^5

时间限制: 1s

空间限制: 512MB