Problem:


Score : 400 points

Problem Statement

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 S_{max} - S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece.
Find the minimum possible value of S_{max} - S_{min}.

Constraints

2 ≤ H, W ≤ 10^5

Input

Input is given from Standard Input in the following format:

H W

Output

Print the minimum possible value of S_{max} - S_{min}.

Sample Input 1

3 5

Sample Output 1

0

In the division below, S_{max} - S_{min} = 5 - 5 = 0.

Sample Input 2

4 5

Sample Output 2

2

In the division below, S_{max} - S_{min} = 8 - 6 = 2.

Sample Input 3

5 5

Sample Output 3

4

In the division below, S_{max} - S_{min} = 10 - 6 = 4.

Sample Input 4

100000 2

Sample Output 4

1

Sample Input 5

100000 100000

Sample Output 5

50000



Sample input:
3 5


Sample output:
0

Submission status: Accepted

Solution code:
import math
import numpy as np

H, W = map(int, input().split())

result = 10**10

def vertical_and_horizontal_cal(h, w):
    global result
    # - | このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area = np.array([i * w, (h-i) * (w//2), (h-i) * (w - w//2)])
        result = min(result, max(area) - min(area))

def vertical_and_vertical_cal(h, w):
    global result
    # - - このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
            area = np.array([i * w,  ((h-i)//2) * w, (h - i - (h-i)//2) * w])
            result = min(result, max(area) - min(area))

vertical_and_horizontal_cal(H, W)
vertical_and_horizontal_cal(W, H)
vertical_and_vertical_cal(H, W)
vertical_and_vertical_cal(W, H)

print(result)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())

Ans = H*W
if H%3==0 or W%3==0:
    Ans = 0
elif H%2==0 and W%2==0:
    Ans = min(H//2,W//2)
else:
    # 全探索するしかない？
    for i in range(1,H):
        t = W//2
        Ans = min(Ans, max(W*i,(H-i)*t,(H-i)*(W-t))-min(W*i,(H-i)*t,(H-i)*(W-t)))
        t = (H-i)//2
        Ans = min(Ans, max(W*i,W*t,W*(H-i-t))-min(W*i,W*t,W*(H-i-t)))
    H,W = W,H
    for i in range(1,H):
        t = W//2
        Ans = min(Ans, max(W*i,(H-i)*t,(H-i)*(W-t))-min(W*i,(H-i)*t,(H-i)*(W-t)))
        t = (H-i)//2
        Ans = min(Ans, max(W*i,W*t,W*(H-i-t))-min(W*i,W*t,W*(H-i-t)))

print(Ans)

Submission status: Accepted

Solution code:
a, b = input().split(" ")
a = int(a)
b = int(b)
if b > a:
    a, b = b, a
case1 = 0
case2 = 0
case3 = 0
case4 = 0
if a % 3 == 0:
    case1 = 0
else:
    case1 = b

if b % 3 == 0:
    case2 = 0
else:
    case2 = a

con1 = round(a / 3)
sum1 = con1 * b

con2 = a - con1
sum2 = b // 2 * con2
sum3 = (b - b // 2) * con2
case3 = (max(sum3, max(sum2, sum1)) - min(sum3, min(sum2, sum1)))

con1 = round(b / 3)
sum1 = con1 *a 

con2 = b - con1
sum2 = a // 2 * con2
sum3 = (a - a // 2) * con2
case4 = (max(sum3, max(sum2, sum1)) - min(sum3, min(sum2, sum1)))

print(min(min(case3,case4), min(case1, case2)))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
if H%3==0 or W%3==0:
    print(0)
    exit()
ans = min(H,W)
if H%2 == 0:
    for w in range(1,W):
        tmp = abs(w*H - (W-w)*H//2)
        ans = min(ans,tmp)
else:
    for w in range(1,W):
        a = w*H
        b = (W-w)*(H//2)
        c = (W-w)*(H//2+1)
        ans = min(ans, max(a,b,c) - min(a,b,c))
if W%2 == 0:
    for h in range(1,H):
        tmp = abs(h*W - (H-h)*W//2)
        ans = min(ans,tmp)
else:
    for h in range(1,H):
        a = h*W
        b = (H-h)*(W//2)
        c = (H-h)*(W//2+1)
        ans = min(ans, max(a,b,c) - min(a,b,c))

print(ans)

Submission status: Accepted

Solution code:
def m():
    h, w = map(int, input().split())
    if h % 3 == 0 or w % 3 == 0:
        return 0
    ans = 9999999999

    for i in range(h):
        if ((h * w) - i * w) % 2 == 0:
            tmp = ((h * w) - i * w) // 2
            ans = min(ans, abs(tmp - (i * w)))
            continue
        c = ((h*w) - i*w) // (h - i)
        tmp = (c // 2) * (h - i)
        another = (c // 2 + 1) * (h - i)
        big = max(tmp, another, i*w)
        small = min(tmp, another, i*w)
        ans = min(ans, abs(big - small))

    for j in range(w):
        if ((h * w) - j*h) % 2 == 0:
            tmp = ((h * w) - j * h) // 2
            ans = min(ans, abs(tmp - (j * h)))
            continue
        c = ((h*w) - j*h) // (w - j)
        tmp = (c // 2) * (w - j)
        another = (c // 2 + 1) * (w - j)
        big = max(tmp, another, j*h)
        small = min(tmp, another, j*h)
        ans = min(ans, abs(big - small))

    return ans
print(m())

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

def main():
    H, W = map(int, input().split())
    def f(H, W):
        ret = H * W
        left = 1
        up = 1
        t = True
        for i in range(1, H):
            a = W * i
            b = (H - i) * (W // 2)
            c = (H - i) * (W // 2 + W % 2)
            maxv = max(a, b, c)
            minv = min(a, b, c)
            ret = min(ret, maxv - minv)
        if H > 2:
            i = 1
            j = 2
            while 1:
                a = W * i
                b = W * j - a
                c = H * W - b - a
                maxv = max(a, b, c)
                minv = min(a, b, c)
                ret = min(ret, maxv - minv)
                if a == minv:
                    if j == H-1 : break
                    i += 1
                    j += 1
                elif b == minv:
                    j += 1
                else:
                    break
        return ret
    print(min(f(H, W), f(W, H)))
main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())


def calc(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    num1, num2 = float("inf"), float("inf")
    for i in range(1, h):
        a = i * w
        b = (h - i) * (w // 2)
        c = (h - i) * (w - w // 2)
        ma = max(a, max(b, c))
        mi = min(a, min(b, c))
        num1 = min(num1, ma - mi)

    for i in range(1, h):
        a = i * w
        p = (h - (h - i) // 2) * w
        q = (h - (h - i + 1) // 2) * w
        mp = max(a, max(p, q))
        mq = min(a, min(p, q))
        num2 = min(num2, mp - mq)

    return min(num1, num2)


print(min(calc(H, W), calc(W, H)))

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys

H, W = map(int, raw_input().split())

ind1 = int(H*W/3)

#first trial
Wp = int(ind1/H)
p1 = H*Wp
Wresid = W-Wp
if Wresid%2 == 0: p2 = p3 = Wresid/2*H
elif H%2 == 0: p2=p3=H/2*Wresid
else:
    Ht, Wt = max([H, Wresid]), min([H, Wresid])
    Hresidspl1 = Ht/2
    Hresidspl2 = Ht-Hresidspl1
    p2 = Wresid*Hresidspl1
    p3 = Wresid*Hresidspl2
ps1 = [p1, p2, p3]
diff1 = max(ps1)-min(ps1)

#second trial
Wp = int(ind1/H)+1
p1 = H*Wp
Wresid = W-Wp
if Wresid%2 == 0: p2 = p3 = Wresid/2*H
elif H%2 == 0: p2 = p3 = H/2*Wresid
else:
    Ht, Wt = max([H, Wresid]), min([H, Wresid])
    Hresidspl1 = Ht/2
    Hresidspl2 = Ht-Hresidspl1
    p2 = Wresid*Hresidspl1
    p3 = Wresid*Hresidspl2
ps2 = [p1, p2, p3]
diff2 = max(ps2)-min(ps2)

#third trial
Hp = int(ind1/W)
p1 = W*Hp
Hresid = H-Hp
if Hresid%2 == 0: p2 = p3 = Hresid/2*W
elif W%2 == 0: p2 = p3 = W/2*Hresid
else:
    Wt, Ht = max([Hresid, W]), min([Hresid, W])
    Wresidspl1 = Wt/2
    Wresidspl2 = Wt-Wresidspl1
    p2 = Hresid*Wresidspl1
    p3 = Hresid*Wresidspl2
ps3 = [p1, p2, p3]
diff3 = max(ps3)-min(ps3)

#fourth trial
Hp = int(ind1/W)+1
p1 = W*Hp
Hresid = H-Hp
if Hresid%2==0: p2 = p3 = Hresid/2*W
elif W%2 == 0: p2 = p3 = W/2*Hresid
else:
    Wt, Ht = max([Hresid, W]), min([Hresid, W])
    Wresidspl1 = Wt/2
    Wresidspl2 = Wt-Wresidspl1
    p2 = Hresid*Wresidspl1
    p3 = Hresid*Wresidspl2
ps4 = [p1, p2, p3]
diff4 = max(ps4)-min(ps4)

print min([diff1, diff2, diff3, diff4])

Submission status: Accepted

Solution code:
length = list(map(int, input().split()))
dif_min = 10000000000
for i in range(2):
    h, w = length[i % 2], length[(i+1) % 2]
    for j in range(1, h):
        s1 = j * w
        h1 = h - j
        s2, s3 = (h1//2) * w, (h1-h1//2) * w
        dif1 = max(s1, s2, s3) - min(s1, s2, s3)

        s2, s3 = h1 * (w//2), h1 * (w-w//2)
        dif2 = max(s1, s2, s3) - min(s1, s2, s3)

        if min(dif1, dif2) < dif_min:
            dif_min = min(dif1, dif2)

print(dif_min)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

if H*W%3==0:
    print(0)
    exit()

ans = H*W

if H%2==0 and W%2==0:
    for k in range(1,W):
        ans = min(ans,max(H*k,(W-k)*(H//2))-min(H*k,(W-k)*(H//2)))
    for k in range(1,H):
        ans = min(ans,max(W*k,(H-k)*(W//2))-min(W*k,(H-k)*(W//2)))
elif H%2==1 and W%2==0:
    for k in range(1,W):
        ans = min(ans,max(H*k,(W-k)*(H//2),(W-k)*(H//2+1))-min(H*k,(W-k)*(H//2),(W-k)*(H//2+1)))
    for k in range(1,H):
        ans = min(ans,max(W*k,(H-k)*(W//2))-min(W*k,(H-k)*(W//2)))
elif H%2==0 and W%2==1:
    for k in range(1,W):
        ans = min(ans,max(H*k,(W-k)*(H//2))-min(H*k,(W-k)*(H//2)))
    for k in range(1,H):
        ans = min(ans,max(W*k,(H-k)*(W//2),(H-k)*(W//2+1))-min(W*k,(H-k)*(W//2),(H-k)*(W//2+1)))
else:
    for k in range(1,W):
        ans = min(ans,max(H*k,(W-k)*(H//2),(W-k)*(H//2+1))-min(H*k,(W-k)*(H//2),(W-k)*(H//2+1)))    
    for k in range(1,H):
        ans = min(ans,max(W*k,(H-k)*(W//2),(H-k)*(W//2+1))-min(W*k,(H-k)*(W//2),(H-k)*(W//2+1)))

for k in range(1,W):
    if (W-k)%2==0:
        ans = min(ans, max(H*k,H*((W-k)//2))-min(H*k,H*((W-k)//2)))
    else:
        ans = min(ans, max(H*k,H*((W-k)//2),H*((W-k)//2+1))-min(H*k,H*((W-k)//2),H*((W-k)//2+1)))
for k in range(1,H):
    if (H-k)%2==0:
        ans = min(ans, max(W*k,W*((H-k)//2))-min(W*k,W*((H-k)//2)))
    else:
        ans = min(ans, max(W*k,W*((H-k)//2),W*((H-k)//2+1))-min(W*k,W*((H-k)//2),W*((H-k)//2+1)))

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans,ans_2,ans_3,ans_4=float("inf"),float("inf"),float("inf"),float("inf")
for i in range(1,w):
    a=h*i
    res=w-i
    if res%2==0:
        b=h*(res//2)
        c=h*(res//2)
    else:
        b=h*(res//2)
        c=h*(res//2+1)
    cut=max(a,b,c)-min(a,b,c)
    ans=min(ans,cut)
for i in range(1,h):
    a_2=i*w
    res_2=h-i
    if res_2%2==0:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2)
    else:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2+1)
    cut_2=max(a_2,b_2,c_2)-min(a_2,b_2,c_2)
    ans_2=min(ans_2,cut_2)
for i in range(1,w):
    a_3=i*h
    res_3=w-i
    if h%2==0:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2)
    else:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2+1)
    cut_3=max(a_3,b_3,c_3)-min(a_3,b_3,c_3)
    ans_3=min(ans_3,cut_3)
for i in range(1,h):
    a_4=w*i
    res_4=h-i
    if w%2==0:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2)
    else:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2+1)
    cut_4=max(a_4,b_4,c_4)-min(a_4,b_4,c_4)
    ans_4=min(ans_4,cut_4)
print(min(ans,ans_2,ans_3,ans_4))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=[]
ans_2=[]
ans_3=[]
ans_4=[]
for i in range(1,w-1):
    a=h*i
    res=w-i
    if res%2==0:
        b=h*(res//2)
        c=h*(res//2)
    else:
        b=h*(res//2)
        c=h*(res//2+1)
    ans.append(max(a,b,c)-min(a,b,c))
for i in range(1,h-1):
    a_2=i*w
    res_2=h-i
    if res_2%2==0:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2)
    else:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2+1)
    ans_2.append(max(a_2,b_2,c_2)-min(a_2,b_2,c_2))
for i in range(1,w-1):
    a_3=i*h
    res_3=w-i
    if h%2==0:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2)
    else:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2+1)
    ans_3.append(max(a_3,b_3,c_3)-min(a_3,b_3,c_3))
for i in range(1,h-1):
    a_4=w*i
    res_4=h-i
    if w%2==0:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2)
    else:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2+1)
    ans_4.append(max(a_4,b_4,c_4)-min(a_4,b_4,c_4))
if len(ans)==0:
    v=float("inf")
else:
    v=min(ans)
if len(ans_2)==0:
    x=float("inf")
else:
    x=min(ans_2)
if len(ans_3)==0:
    y=float("inf")
else:
    y=min(ans_3)
if len(ans_4)==0:
    z=float("inf")
else:
    z=min(ans_4)
f=float("inf")
if min(v,x,y,z)==f:
    print(1)
else:
    print(min(v,x,y,z))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())

if H%3==0 or W%3==0:
    print(0)
    exit()

ans = min(H,W)
if H%2==0:
    for w in range(1,W):
        s1 = w*H
        s2 = (W-w)*H//2
        ans = min(ans, abs(s1 - s2))
if W%2==0:
    for h in range(1,H):
        s1 = h*W
        s2 = (H-h)*W//2
        ans = min(ans, abs(s1 - s2))

for h in range(H//2,H//2+2):
    if h >= H: break
    for w in range(W//2,W//2+2):
        if w >= W: break
        s1 = h*W
        s2 = (H-h)*w
        s3 = (H-h)*(W-w)
        ans = min(ans, s1, s2, s3)

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if (h%3)*(w%3)==0:
    print(0)
    exit()
else:
    hh=(h*w)//3//h
    ww=(h*w)//3//w
    a=max(hh*h,(w-hh)*(h//2),(w-hh)*(h-h//2))-min(hh*h,(w-hh)*(h//2),(w-hh)*(h-h//2))
    b=max(ww*w,(h-ww)*(w//2),(h-ww)*(w-w//2))-min(ww*w,(h-ww)*(w//2),(h-ww)*(w-w//2))
    c=max((hh+1)*h,(w-hh-1)*(h//2),(w-hh-1)*(h-h//2))-min((hh+1)*h,(w-hh-1)*(h//2),(w-hh-1)*(h-h//2))
    d=max((ww+1)*w,(h-ww-1)*(w//2),(h-ww-1)*(w-w//2))-min((ww+1)*w,(h-ww-1)*(w//2),(h-ww-1)*(w-w//2))
    print(min(a,b,c,d,h,w))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = float('Inf')
l = [float('Inf')]*4
for i in range(1, max(h, w)):
  a, b, c, d = l
  if i <= h:
    a = abs(max(i*w, (h-i)//2*w, (h-i-(h-i)//2)*w) - min(i*w, (h-i)//2*w, (h-i-(h-i)//2)*w))
    b = abs(max(i*w, (h-i)*(w//2), (h-i)*(w-w//2)) - min(i*w, (h-i)*(w//2), (h-i)*(w-w//2)))  

  if i <= w:
    c = abs(max(i*h, (w-i)//2*h, (w-i-(w-i)//2)*h) - min(i*h, (w-i)//2*h, (w-i-(w-i)//2)*h))
    d = abs(max(i*h, (w-i)*(h//2), (w-i)*(h-h//2)) - min(i*h, (w-i)*(h//2), (w-i)*(h-h//2)))
  
  if min(a, b, c, d) < ans:
    ans = min(a, b, c, d)

print(ans)

Submission status: Accepted

Solution code:
def s(a1, a2, a3): return max([a1, a2, a3]) - min([a1, a2, a3])

h, w = map(int, input().split())
h1 = h // 3
h2 = (h - h1) // 2
h3 = h - h1 - h2
t = s(h1 * w, h2 * w, h3 * w)
w1 = w // 3
w2 = (w - w1) // 2
w3 = w - w1 - w2
t = min(t, s(h * w1, h * w2, h * w3))
w1 = w // 3
w2 = w - w1
h1 = h // 2
h2 = h - h1
t = min(t, s(h * w1, h1 * w2, h2 * w2))
w1 = (w // 3) + 1
w2 = w - w1
t = min(t, s(h * w1, h1 * w2, h2 * w2))
h1 = h // 3
h2 = h - h1
w1 = w // 2
w2 = w - w1
t = min(t, s(h1 * w, h2 * w1, h2 * w2))
h1 = h // 3 + 1
h2 = h - h1
t = min(t, s(h1 * w, h2 * w1, h2 * w2))
print(t)

Submission status: Accepted

Solution code:
def choco(m,n):
	if m%2==0:
		return [m*n//2,m*n//2]
	else:
		if m==1: return [(n-n%2)//2,(n+n%2)//2]
		else: return [(m-1)*n//2,(m+1)*n//2]

h,w = (int(i) for i in input().split())
answer = h*w
for i in range(1,h):
	x,y = [],[]
	x.append(i*w)
	y.append(i*w)
	x += choco(h-i,w)
	y += choco(w,h-i)
	num = min(max(x)-min(x),max(y)-min(y))
	if num<answer:
		answer = num
for j in range(1,w):
	x,y = [],[]
	x.append(j*h)
	y.append(j*h)
	x += choco(w-j,h)
	y += choco(h,w-j)
	num = min(max(x)-min(x),max(y)-min(y))
	if num<answer:
		answer = num
print(answer)

Submission status: Accepted

Solution code:
import math
h , w = map(int, input().split())
dh, dw = [], []
rh, rw = h, w
area = []
for i in range(3,0,-1):
    dh.append(rh//i)
    rh -= dh[3-i]
    dw.append(rw//i)
    rw -= dw[3-i]

for i in range(3):
    area.append(dw[i]*h)
ans = max(area)-min(area)

area=[]
for i in range(3):
    area.append(dh[i]*w)
ans = min(ans,max(area)-min(area))

for i in range(0,3,2):
    area = []
    area.append(dw[i]*h)
    area.append((w-dw[i])*math.ceil(h/2))
    area.append((w-dw[i])*math.floor(h/2))
    ans = min(ans, (max(area)-min(area)))

for i in range(0,3,2):
    area = []
    area.append(dh[i]*w)
    area.append((h-dh[i])*math.ceil(w/2))
    area.append((h-dh[i])*math.floor(w/2))
    ans = min(ans, (max(area)-min(area)))
print(ans)

Submission status: Accepted

Solution code:
import math
h,w = map(int,input().split())
lis = []

a = math.floor(h/3)
b = math.ceil(h/3)
c = h-(a + b)
lis.append(w * (max(a,b,c)-min(a,b,c)))

biga = math.ceil(h/3)
smalla = math.floor(h/3)
if biga-(h/3) >= (h/3)-smalla:
    a = smalla
else:
    a = biga
b = math.ceil(w/2)
c = w - b
b *= (h-a)
c *= (h-a)
a *= w
lis.append(max(a,b,c)-min(a,b,c))

a = math.floor(w/3)
b = math.ceil(w/3)
c = w-(a + b)
lis.append(h * (max(a,b,c)-min(a,b,c)))

biga = math.ceil(w/3)
smalla = math.floor(w/3)
if biga-(w/3) >= (w/3)-smalla:
    a = smalla
else:
    a = biga
b = math.ceil(h/2)
c = h - b
b *= (w-a)
c *= (w-a)
a *= h
lis.append(max(a,b,c)-min(a,b,c))

print(min(lis))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
else:
  ans=10000000000000
  h=H//3
  w=W//2
  ptn1=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn1)-min(ptn1))
  
  h=H//3+1
  w=W//2
  ptn2=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn2)-min(ptn2))
  
  h=H//3+1
  w=W//2+1
  ptn3=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn3)-min(ptn3))
  
  h=H//3
  w=W//2+1
  ptn4=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn4)-min(ptn4))
  
  h=H//3
  ptn5=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn5)-min(ptn5))
  
  h=H//3+1
  ptn6=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn6)-min(ptn6))

  H,W=W,H
  h=H//3
  w=W//2
  ptn1=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn1)-min(ptn1))
  
  h=H//3+1
  w=W//2
  ptn2=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn2)-min(ptn2))
  
  h=H//3+1
  w=W//2+1
  ptn3=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn3)-min(ptn3))
  
  h=H//3
  w=W//2+1
  ptn4=[h*W,(H-h)*w,(H-h)*(W-w)]
  ans=min(ans,max(ptn4)-min(ptn4))
    
  h=H//3
  ptn5=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn5)-min(ptn5))
  
  h=H//3+1
  ptn6=[h*W,(H-h*2)*W]
  ans=min(ans,max(ptn6)-min(ptn6))
  
  print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
DH=10**15
DW=10**15
for h1 in range(1,h+1):
  h2=(h-h1)//2
  h3=h-h1-h2
  w1=w
  w2=w
  w3=w
  s1=h1*w1
  s2=h2*w2
  s3=h3*w3
  S=[s1,s2,s3]
  d0=max(S)-min(S)
  h2=h-h1
  h3=h-h1
  w1=w
  w2=w//2
  w3=w-w2
  s1=h1*w1
  s2=h2*w2
  s3=h3*w3
  S=[s1,s2,s3]
  d1=max(S)-min(S)
  DH=min([DH,d0,d1])
  
hx,wx=h,w
w=hx
h=wx
for h1 in range(1,h+1):
  h2=(h-h1)//2
  h3=h-h1-h2
  w1=w
  w2=w
  w3=w
  s1=h1*w1
  s2=h2*w2
  s3=h3*w3
  S=[s1,s2,s3]
  d0=max(S)-min(S)
  h2=h-h1
  h3=h-h1
  w1=w
  w2=w//2
  w3=w-w2
  s1=h1*w1
  s2=h2*w2
  s3=h3*w3
  S=[s1,s2,s3]
  d1=max(S)-min(S)
  DW=min([DW,d0,d1])
  
print(min(DH,DW))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if (H*W)%3==0:
    print(0)
    exit()
S=[H, W]
x=H//3
a=x*W;b=(H-x)*(W//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
x+=1
a=x*W;b=(H-x)*(W//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
y=W//3
a=y*H;b=(W-y)*(H//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
y+=1
a=y*H;b=(W-y)*(H//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
print(min(S))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())

def solve(tate,yoko):
    a_min = 100000000000
    if tate % 3 == 0 or yoko % 3 == 0:
        return 0
    for i in range(1,tate+1):
        s1 = i * yoko
        s2 = (tate - i) * (yoko // 2)
        s3 = (tate - i) * (yoko // 2 + yoko % 2)
        ans1 = max(s1,s2,s3) - min(s1,s2,s3)  
        
        t1 = i * yoko
        t2 = yoko * ((tate - i) // 2)
        t3 = yoko * ((tate - i) // 2 + (tate - i) % 2)
        ans2 = max(t1,t2,t3) - min(t1,t2,t3)
        
        ans = min(ans1,ans2)
        
        if a_min > ans :
            a_min = ans
    
    return a_min 
    
print(min(solve(h,w),solve(w,h)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
import math
if h%3==0 or w%3==0:
    print(0)
    exit()
w_i=w//2
ans=[]
for i in range(1,h):
    sa=i*w
    sb=(h-i)*w_i
    sc=(h-i)*(w-w_i)
    ans.append(max(sa,sb,sc)-min(sa,sb,sc))
v=min(ans)
ans_3=[]
for l in range(1,h):
    h_half=(h-l)//2
    sa=w*l
    sb=w*h_half
    sc=w*((h-l)-h_half)
    ans_3.append(max(sa,sb,sc)-min(sa,sb,sc))
v_3=min(ans_3)
ans_i=[]
h_i=h//2
for j in range(1,w):
    sa=j*h
    sb=(w-j)*(h_i)
    sc=(w-j)*(h-h_i)
    ans_i.append(max(sa,sb,sc)-min(sa,sb,sc))
v_i=min(ans_i)
ans_2=[]
for k in range(1,w):
    w_half=(w-k)//2
    sa=h*k
    sb=h*w_half
    sc=h*((w-k)-w_half)
    ans_2.append(max(sa,sb,sc)-min(sa,sb,sc))
v_2=min(ans_2)
print(min(v,v_i,v_2,v_3))
#86 5

Submission status: Accepted

Solution code:
h,w = sorted(list(map(int,input().split())))
if h % 3 == 0 or w % 3 == 0:
  ans = 0
else:
  c1 = ((w//3+1)*h)-((w-1-w//3)*(h//2))
  c2 = ((w-w//3)*(h-h//2))-(w//3*h)
  c3 = h
  c4 = ((h//3+1)*w)-((h-1-h//3)*(w//2))
  c5 = ((h-h//3)*(w-w//2))-(h//3*w)
  ans = min(c1,c2,c3,c4,c5)
print(ans)

Submission status: Accepted

Solution code:
def c_ChocolateBar(H, W):
    ans = float('inf')
    # for文の順は解説における矩形の分け方の図の左からの順と一致
    for h in range(1, H):
        S_A = h * W
        hh = (H - h) // 2
        S_B = hh * W
        S_C = (H - h - hh) * W
        ans = min(ans, max([S_A, S_B, S_C]) - min([S_A, S_B, S_C]))
    for h in range(1, H):
        S_A = h * W
        w = W // 2
        S_B = (H - h) * w
        S_C = (H - h) * (W - w)
        ans = min(ans, max([S_A, S_B, S_C]) - min([S_A, S_B, S_C]))
    for w in range(1, W):
        S_A = H * w
        ww = (W - w) // 2
        S_B = H * ww
        S_C = H * (W - w - ww)
        ans = min(ans, max([S_A, S_B, S_C]) - min([S_A, S_B, S_C]))
    for w in range(1, W):
        S_A = H * w
        h = H // 2
        S_B = h * (W - w)
        S_C = (H - h) * (W - w)
        ans = min(ans, max([S_A, S_B, S_C]) - min([S_A, S_B, S_C]))
    return ans
H,W = [int(i) for i in input().split()]
print(c_ChocolateBar(H, W))

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))


def France():
    """
    ABC
    ABC
    ABC
    """
    d, m = divmod(w, 3)
    if m == 0:
        return 0
    return h

def Germany():
    """
    AAA
    BBB
    CCC
    """
    d, m = divmod(h, 3)
    if m == 0:
        return 0
    return w

def Chile():
    """
    AB
    AB
    CC
    """
    hd, hm = divmod(h, 3)
    wd, wm = divmod(w, 2)
    found = w*h
    for i in range(2*hd, 2*hd+3):
        for j in range(wd, wd+3):
            A = i * j 
            B = i * (w - j)
            C = (h - i) * w
            D = max(A, B, C) - min(A, B, C)
            found = min(found, D)
    return found

def Madagascar():
    """
    ABB
    ACC
    """
    hd, hm = divmod(h, 2)
    wd, wm = divmod(w, 3)
    found = w*h
    for i in range(wd, wd+3):
        for j in range(hd, hd+3):
            A = i * h
            B = (w - i) * j
            C = (h - j) * (w - i)
            D = max(A, B, C) - min(A, B, C)
            found = min(found, D)
    return found

print(min(France(), Germany(), Chile(), Madagascar()))

Submission status: Accepted

Solution code:
h,w = sorted(list(map(int,input().split())))
if h % 3 == 0 or w % 3 == 0:
  ans = 0
else:
  c1 = ((w//3+1)*h)-((w-1-w//3)*(h//2))
  c2 = ((w-w//3)*(h-h//2))-(w//3*h)
  c3 = h
  c4 = ((h//3+1)*w)-((h-1-h//3)*(w//2))
  c5 = ((h-h//3)*(w-w//2))-(h//3*w)
  ans = min(c1,c2,c3,c4,c5)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = []
if h%3 == 0 or w%3 == 0:
	print('0')
else:
	a = h
	s = []
	if a%2 == 0:
		d = a/2
		if w%3 == 1:
			b = (w-1)/3
			c = w - b
			s.append(a*b)
			s.append(c*d)
		else:
			b = (w+1)/3
			c = w-b
			s.append(a*b)
			s.append(c*d)
	else:
		d = (a-1)/2
		if w%3 == 1:
			b = (w-1)/3
			c = w - b
			s.append(a*b)
			s.append(c*d)
			s.append(c*(d+1))
		else:
			b = (w+1)/3
			c = w-b
			s.append(a*b)
			s.append(c*d)
			s.append(c*(d+1))
	ans.append(abs(int(max(s)-min(s))))
	x = w
	w = h
	h = x
	if h%3 == 0 or w%3 == 0:
		print('0')
	else:
		a = h
		k = []
		if a%2 == 0:
			d = a/2
			if w%3 == 1:
				b = (w-1)/3
				c = w - b
				k.append(a*b)
				k.append(c*d)
			else:
				b = (w+1)/3
				c = w-b
				k.append(a*b)
				k.append(c*d)
		else:
			d = (a-1)/2
			if w%3 == 1:
				b = (w-1)/3
				c = w - b
				k.append(a*b)
				k.append(c*d)
				k.append(c*(d+1))
			else:
				b = (w+1)/3
				c = w-b
				k.append(a*b)
				k.append(c*d)
				k.append(c*(d+1))
		ans.append(abs(int(max(k)-min(k))))
	ans.append(h)
	ans.append(w)
	print(min(ans))

Submission status: Accepted

Solution code:
print((lambda a:min([min([float("inf")if a[1]<=1 else(lambda b:b[2]-b[0])(sorted([i*a[0],(a[1]-i)*(a[0]//2),(a[1]-i)*(a[0]//2+(a[0]%2))]))for i in range(1, a[1])])]+[min([float("inf")if a[0]<=1 else(lambda b:b[2]-b[0])(sorted([i*a[1],(a[0]-i)*(a[1]//2),(a[0]-i)*(a[1]//2+(a[1]%2))]))for i in range(1, a[0])])]+[a[1]if a[0]%3 else 0]+[a[0]if a[1]%3 else 0]))(list(map(int,input().split()))))

Submission status: Accepted

Solution code:
print((lambda a:min([min([float("inf") if a[1]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[0],(a[1]-i)*(a[0]//2),(a[1]-i)*(a[0]//2+(a[0]%2))])) for i in range(1, a[1])])]+[min([float("inf") if a[0]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[1],(a[0]-i)*(a[1]//2),(a[0]-i)*(a[1]//2+(a[1]%2))])) for i in range(1, a[0])])]+[a[1] if a[0]%3 else 0]+[a[0] if a[1]%3 else 0]))(list(map(int,input().split()))))

Submission status: Accepted

Solution code:
print((lambda a:min([min([1145148931919810 if a[1]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[0],(a[1]-i)*(a[0]//2),(a[1]-i)*(a[0]//2+(a[0]%2))])) for i in range(1, a[1])])]+[min([1145148931919810 if a[0]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[1],(a[0]-i)*(a[1]//2),(a[0]-i)*(a[1]//2+(a[1]%2))])) for i in range(1, a[0])])]+[a[1] if a[0]%3 else 0]+[a[0] if a[1]%3 else 0]))(list(map(int,input().split()))))

Submission status: Accepted

Solution code:
H,W=map(int, raw_input().split())
#print H,W

c=[-1,0,1,2]

#tate,tate
def calc_t_t(h,w):
	if w%3==0:
		A1=h*int(w/3)
		A2=h*int(w/3)
		A3=h*w-A1-A2
	else:
		A1=h*(w/3)
		A2=h*((w-int(w/3))/2)
		A3=h*w-A1-A2
	a=[A1,A2,A3]
	#print a
	return max(a)-min(a)


#tate,yoko
def calc_t_y(h,w):
	a=[]
	if w==2:
		A1=h*w/2
		A2=1*h/2
		A3=h*w-A1-A2
		a.append([A1,A2,A3])
	else:

		w_tmp=int(h*w/3)/h
		#print w_tmp
		for j in c:
			if w_tmp+j<=w and w>0:
				A1=h*(w_tmp+j)
				A2=h/2*(w-(w_tmp+j))
				A3=h*w-A1-A2
				a.append([A1,A2,A3])
			


	#print a
	min_a=0
	for i in a:
		if min_a==0 or min_a>max(i)-min(i):
			min_a=max(i)-min(i)
	return min_a

b=[]
b.append(calc_t_t(H,W))
b.append(calc_t_t(W,H))
b.append(calc_t_y(H,W))
b.append(calc_t_y(W,H))

print min(b)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
ans = H*W 

for loop in xrange(2):
    ans = min(ans, (((H - H/3) + 1)/2 - H/3)*W)
    for w in xrange(1, W):
        h = H/2
        mx = max(w*H, (W - w)*(H - h))
        mn = min(w*H, (W - w)*h)
        ans = min(ans, mx - mn)
    H, W = W, H

print ans

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

ret = float('inf')
for h0 in range(1, H):
    h1 = (H - h0) // 2
    h2 = H - h0 - h1
    if not (h1 == 0 or h2 == 0):
        S_max = max(h0 * W, h1 * W, h2 * W)
        S_min = min(h0 * W, h1 * W, h2 * W)
        ret = min(ret, S_max - S_min)

    w1 = W // 2
    w2 = W - w1
    if not (w1 == 0 or w2 == 0):
        S_max = max(h0 * W, (H - h0) * w1, (H - h0) * w2)
        S_min = min(h0 * W, (H - h0) * w1, (H - h0) * w2)
        ret = min(ret, S_max - S_min)
        
for w0 in range(1, W):
    h1 = H // 2
    h2 = H - h1
    if not (h1 == 0 or h2 == 0):
        S_max = max(H * w0, h1 * (W - w0), h2 * (W - w0))
        S_min = min(H * w0, h1 * (W - w0), h2 * (W - w0))
        ret = min(ret, S_max - S_min)

    w1 = (W - w0) // 2
    w2 = W - w0 - w1
    if not (w1 == 0 or w2 == 0):
        S_max = max(H * w0, H * w1, H * w2)
        S_min = min(H * w0, H * w1, H * w2)
        ret = min(ret, S_max - S_min)

print(ret)

Submission status: Accepted

Solution code:
import math
H , W = map(int,input().split())
S = set()

def half_cut(x,y):
    for i in range(1,x):
        S1 = (x-i)*y
        S2 = math.ceil(y/2)*i
        S3 = math.floor(y/2)*i
        S.add(max(S1,S2,S3)-min(S1,S2,S3))

def three_cut(x,y):
    for i in range(1,x):
        S1 = math.ceil(i/2)*y
        S2 = math.floor(i/2)*y
        S3 = (x-i)*y
        S.add(max(S1,S2,S3)-min(S1,S2,S3))

half_cut(H,W)
half_cut(W,H)
three_cut(H,W)
three_cut(W,H)

print(min(S))

Submission status: Accepted

Solution code:
H, W = [int(n) for n in input().split()]


def calc(H, W):
  res = 10000000000
  for h in range(1, H):
    S1 = h*W
    S2a = (H-h)*(W//2)
    S3a = (H-h)*(W-W//2)
    S2b = (H-h)//2*W
    S3b = ((H-h)- (H-h)//2)*W
    dS = min( max(S1, S2a, S3a)-min(S1, S2a, S3a), max(S1, S2b, S3b) - min(S1, S2b, S3b))
    if dS < res:
      res = dS
  return res

print(min(calc(H,W), calc(W,H)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc062.contest.atcoder.jp/tasks/arc074_a

"""
import sys
from sys import stdin
from math import ceil
input = stdin.readline


def main(args):
    H, W = map(int, input().split())

    p1 = -1
    p2 = -1
    p3 = -1
    min_diff = H * W

    for i in range(1, (H//2)+1):
        p1 = i * W              #  横に割る
        reH = H - i
        # 残りを横に割った場合
        p2 = ceil(reH / 2) * W
        p3 = (H * W) - p1 - p2
        diff = max(p1, p2, p3) - min(p1, p2, p3)
        if diff < min_diff:
            min_diff = diff

        # 残りを縦に割った場合
        p2 = ceil(W / 2) * reH
        p3 = (H * W) - p1 - p2
        diff = max(p1, p2, p3) - min(p1, p2, p3)
        if diff < min_diff:
            min_diff = diff

    # HとWを入れ替えて同じ計算
    temp = H
    H = W
    W = temp
    for i in range(1, (H//2)+1):
        p1 = i * W              #  横に割る
        reH = H - i
        # 残りを横に割った場合
        p2 = ceil(reH / 2) * W
        p3 = (H * W) - p1 - p2
        diff = max(p1, p2, p3) - min(p1, p2, p3)
        if diff < min_diff:
            min_diff = diff

        # 残りを縦に割った場合
        p2 = ceil(W / 2) * reH
        p3 = (H * W) - p1 - p2
        diff = max(p1, p2, p3) - min(p1, p2, p3)
        if diff < min_diff:
            min_diff = diff

    print(min_diff)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import math
H,W = map(int,input().split())

if H%3==0 or W%3==0:
    print(0)
elif H==2 and W==2:
    print(1)
else:
    def cal2(h,w):
        x1,x2 = math.floor(w/2),math.ceil(w/2)
        y1,y2 = math.floor((2*h)/3),math.ceil((2*h)/3)
        def cal(x,y):
            return max(x*y,(w-x)*y,(h-y)*w) - min(x*y,(w-x)*y,(h-y)*w)
        return min(cal(x1,y1),cal(x2,y1),cal(x1,y2),cal(x2,y2))

    if H==2 or W ==2:
        print(min(cal2(H,W),cal2(W,H),max(H,W)))
    else:
        print(min(cal2(H,W),cal2(W,H),H,W))

Submission status: Accepted

Solution code:
import math
H,W = map(int,input().split())

if H%3==0 or W%3==0:
    print(0)
elif H==2 and W==2:
    print(1)
else:

    def cal(x,y):
        return max(x*y,(W-x)*y,(H-y)*W) - min(x*y,(W-x)*y,(H-y)*W)

    x1,x2 = math.floor(W/2),math.ceil(W/2)
    y1,y2 = math.floor((2*H)/3),math.ceil((2*H)/3)

    ans1 = min(cal(x1,y1),cal(x2,y1),cal(x1,y2),cal(x2,y2))

    W,H = H,W
    x1,x2 = math.floor(W/2),math.ceil(W/2)
    y1,y2 = math.floor((2*H)/3),math.ceil((2*H)/3)

    ans2 = min(cal(x1,y1),cal(x2,y1),cal(x1,y2),cal(x2,y2))

    if H ==2 or W == 2:
        print(min(ans1,ans2,max(H,W)))
    else:
        print(min(ans1,ans2,H,W))