Problem Description
There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.
Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize Smax - Smin, where Smax is the area (the number of blocks contained) of the largest piece, and Smin is the area of the smallest piece. Find the minimum possible value of Smax−Smin.
Constraints
2≤H,W≤105
Input
Input is given from Standard Input in the following format:
H W
Output
Print the minimum possible value of Smax−Smin.
Example
Sample Input 1
3 5
Sample Output 1
0 In the division below, Smax−Smin=5−5=0.
Sample Input 2
4 5
Sample Output 2
2 In the division below, Smax−Smin=8−6=2.
Sample Input 3
5 5
Sample Output 3
4 In the division below, Smax−Smin=10−6=4.
Sample Input 4
100000 2
Sample Output 4
1
Sample Input 5
100000 100000
Sample Output 5
50000
题意：给出一个矩形的长、宽，现在要将这个矩形分成三份，使得这三份中的最大值与最小值的面积的差最小，求这个差
思路：由于要分成三份，那么最多切两刀，那么要使得差最小，就要使面积相近，因此切法只有两种：一种平行着切三刀，一种先一刀分成两半，再将一半中平分成两半，因此对于两种切法分别从长、宽枚举比较求最小值即可
Source Program
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 500+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
LL max(LL a,LL b,LL c){
return max(a,max(b,c));
}
LL min(LL a,LL b,LL c){
return min(a,min(b,c));
}
int main(){
LL h,w;
scanf("%lld%lld",&h,&w);
LL res=INF;
LL pos;
LL a,b,c;
LL maxx,minn;
for(LL i=1;i<h;i++){
pos=(h-i)/2;
a=pos*w;
b=(h-i-pos)*w;
c=i*w;
maxx=max(a,b,c);
minn=min(a,b,c);
res=min(maxx-minn,res);
pos=w/2;
a=pos*(h-i);
b=(w-pos)*(h-i);
c=i*w;
minn=min(a,b,c);
maxx=max(a,b,c);
res=min(maxx-minn,res);
}
for(LL i=1;i<w;i++){
pos=(w-i)/2;
a=pos*h;
b=(w-i-pos)*h;
c=i*h;
minn=min(a,b,c);
maxx=max(a,b,c);
res=min(maxx-minn,res);
pos=h/2;
a=pos*(w-i);
b=(h-pos)*(w-i);
c=i*h;
minn=min(a,b,c);
maxx=max(a,b,c);
res=min(maxx-minn,res);
}
printf("%lld\n",res);
return 0;
}
