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
h, w = map(int,input().split())
hw = h * w
r = hw

for i in range(math.floor(h / 3), math.ceil(h / 3) + 1):
    r1 = w * i
    for i1 in range(math.floor((h-i) / 2), math.ceil((h-i) / 2) + 1):
        r2 = i1 * w
        r3 = hw - r1 - r2
        if r3 == 0:
            pass
        
        r = r if (max(r1,r2,r3) - min(r1,r2,r3)) > r else (max(r1,r2,r3) - min(r1,r2,r3))

    for i2 in range(math.floor(w / 2), math.ceil(w / 2) + 1):
        r2 = i2 * (h - i)
        r3 = hw - r1 - r2
        if r3 == 0:
            pass
        r = r if (max(r1, r2, r3) - min(r1, r2, r3)) > r else (max(r1, r2, r3) - min(r1, r2, r3))

for j in range(math.floor(w / 3), math.ceil(w / 3) + 1):
    r1 = h * j
    for j1 in range(math.floor((w-j) / 2), math.ceil((w-j) / 2) + 1):
        r2 = j1 * h
        r3 = hw - r1 - r2
        if r3 == 0:
            pass
        r = r if (max(r1,r2,r3) - min(r1,r2,r3)) > r else (max(r1,r2,r3) - min(r1,r2,r3))
    for j2 in range(math.floor(h / 2), math.ceil(h / 2) + 1):
        r2 = j2 * (w - j)
        r3 = hw - r1 - r2
        if r3 == 0:
            pass
        r = r if (max(r1, r2, r3) - min(r1, r2, r3)) > r else (max(r1, r2, r3) - min(r1, r2, r3))

print(r)

Submission status: Accepted

Solution code:
#062_C
h,w=map(int,input().split())
if (h*w)%3==0:
    print(0)
else:
    #縦or横3分割
    ans=min(h,w)
    #縦→横or横→縦
    for x in [h//3,h//3+1]:
        ans=min(ans,max(x*w,(h-x)*(w//2),(h-x)*(w-w//2))-min(x*w,(h-x)*(w//2),(h-x)*(w-w//2)))
    for y in [w//3,w//3+1]:
        ans=min(ans,max(y*h,(w-y)*(h//2),(w-y)*(h-h//2))-min(y*h,(w-y)*(h//2),(w-y)*(h-h//2)))
    print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()

ans = float('inf')
for _ in range(2):
    for i in [H//3,H//3+1]:
        a = i*W
        b = ((H - i)//2)*W
        c = ((H - i + 1)//2)*W
        ans = min(ans, abs(max(a, b, c) - min(a, b, c)))

        b = (H-i)*(W//2)
        c = (H-i)*((W + 1)//2)
        ans = min(ans, abs(max(a, b, c) - min(a, b, c)))
    H, W = W, H
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    if H % 3 == 0 or W % 3 == 0:
        return 0
    m = 10**9
    # case H
    m = min(H, m)
    # case W
    m = min(W, m)
    # case rei 2
    g = H * (W // 3)
    b = (W - (W // 3)) * (H // 2)
    r = H * W - g - b
    m = min(m, max(abs(g-b), abs(g-r), abs(b-r)))
    # case rei 2-2
    g = H * ((W // 3) + 1)
    b = (W - (W // 3) - 1) * (H // 2)
    r = H * W - g - b
    m = min(m, max(abs(g-b), abs(g-r), abs(b-r)))
    # case rei 3
    g = W * (H // 3)
    b = (H - (H // 3)) * (W // 2)
    r = H * W - g - b
    m = min(m, max(abs(g-b), abs(g-r), abs(b-r)))
    # case rei 3-2
    g = W * ((H // 3) + 1)
    b = (H - (H // 3)-1) * (W // 2)
    r = H * W - g - b
    m = min(m, max(abs(g-b), abs(g-r), abs(b-r)))
    return m
print(main())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
areas = [[] for _ in range(4)]

h1 = round(H/3)
areas[0].append(h1*W)
areas[1].append(h1*W)
H -= h1
h2 = round(H/2)
w2 = round(W/2)
areas[0].append(h2*W)
areas[0].append((H-h2)*W)
areas[1].append(H*w2)
areas[1].append(H*(W-w2))

H += h1

w1 = round(W/3)
areas[2].append(H*w1)
areas[3].append(H*w1)
W -= w1
h2 = round(H/2)
w2 = round(W/2)
areas[2].append(h2*W)
areas[2].append((H-h2)*W)
areas[3].append(H*w2)
areas[3].append(H*(W-w2))

ans = H*W
for area in areas:
    area.sort()
    ans = min(ans, area[2] - area[0])
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
 
if h%3 == 0 or w%3 == 0:
    ans = 0
    
else:
    ans = float('inf')
    
    # 縦(横)で2つに分割して、そのうちの1つを横(縦)で分割する
    for x, y in [[h, w], [w, h]]:
        mid = x//2
        r = x%2
        temp = float('inf')
        for i in range(1, y):
            a, b, c = x*i, (mid+r)*(y-i), (mid)*(y-i)
            area = abs(max(a, b, c) - min(a, b, c))
            if area < temp:
                temp = area
            else:
                break
        ans = min(ans, temp)
        
    # 縦(横)で3つに分割する
    for x, y in [[h, w], [w, h]]:
        ans = min(ans, x*(y//3+1) - x*(y//3))
    
print(ans)

Submission status: Accepted

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

h1,h2 = h//3, h//3+1
w1,w2= min(w//2, w//2+1), max(w//2, w//2+1)
h3,h4 = min(h//2, h//2+1), max(h//2, h//2+1)
w3,w4 = w//3, w//3+1

ans = []

a,b,c = h1*w, (h-h1)*w1, (h-h1)*w2
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = h2*w, (h-h2)*w1, (h-h2)*w2
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = w3*h, (w-w3)*h3, (w-w3)*h4
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = w4*h, (w-w4)*h3, (w-w4)*h4
ans.append(max([a,b,c])-min([a,b,c]))

ans.append(h)
ans.append(w)

if w%2==0:
  ans.append(abs(h1*w-(h-h1)*w//2))
  ans.append(abs(h2*w-(h-h2)*w//2))

if h%2==0:
  ans.append(abs(w3*h-(w-w3)*h//2))
  ans.append(abs(w4*h-(w-w4)*h//2))
  
if h%3==0 or w%3==0:
  ans.append(0)
  
print(min(ans))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
 
if h%3 == 0 or w%3 == 0:
    print(0)
    exit()
 
#print(h, w)
min_ = float('inf')
for i in range(1, h):
    s1 = w*i
    s2 = (h-i)*(w//2)
    s3 = (h-i)*(w-w//2)
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)
 
    s2 = ((h-i)//2)*w
    s3 = ((h-i) - (h-i)//2)*w
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)
 
#print('-')
 
for i in range(1, w):
    s1 = h*i
    s2 = (w-i)*(h//2)
    s3 = (w-i)*(h-h//2)
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)
 
    s2 = ((w-i)//2)*h
    s3 = ((w-i) - (w-i)//2)*h
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)
 
print(min_)

Submission status: Accepted

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

def f(a, b):
	mod = b % 3
	if mod == 0:
		return 0
	else:
		return 1 

# カットする線が全て平行
# 縦にカットした場合、 W // 3 が2つと、 W - 2 * (W // 3) が1つできるから、この2つの差を取る
dif = H * f(H, W)
ans = min(ans, dif)
# print(ans)

# 横にカットした場合も同様
# 横にカット
dif = W * f(W, H)
ans = min(ans, dif)
# print(ans)

# 平行ではない
# 大きく縦にカット
for i in range(W):
	s_1 = H * i
	aft_W = W - i
	# 横にカットするやり方は先と同様
	s_2 = aft_W * (H // 2)
	s_3 = aft_W * (H - H // 2)
	
	dif = max(s_1, s_2, s_3) - min(s_1, s_2, s_3)
	ans = min(ans, dif)
	
# print(ans)
	
	
# 大きく横にカット
for i in range(H):
	s_1 = W * i
	aft_H = H - i
	# 縦にカットするやり方は先と同様
	s_2 = aft_H * (W // 2)
	s_3 = aft_H * (W - W // 2)
	
	dif = max(s_1, s_2, s_3) - min(s_1, s_2, s_3)
	ans = min(ans, dif)
	
	
print(ans)

Submission status: Accepted

Solution code:
def calc(a, b, c):
    return max(a, b, c) - min(a, b, c)


h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    ans0 = min(h, w)
    ans1 = h * w

    for i in range(1, h+1):
        s1 = i * w
        if w % 2 == 0:
            x = w // 2
            s2 = (h-i) * x
            s3 = s2
        else:
            x = w // 2 + 1
            s2 = (h-i) * x
            s3 = (h-i) * (w-x)
        ans1 = min(ans1, calc(s1, s2, s3))


    ans2 = h * w
    for i in range(1, w+1):
        s1 = i * h
        if h % 2 == 0:
            x = h // 2
            s2 = (w - i) * x
            s3 = s2
        else:
            x = h // 2 + 1
            s2 = (w - i) * x
            s3 = (w - i) * (h - x)
        ans2 = min(ans2, calc(s1, s2, s3))

    ans = min(ans0, ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ass = 10**9
if h%3 == 0:
    ass = 0
else:
    ass = w

if w % 3 == 0:
    ass = 0
else:
    ass = min(ass,h)


if h % 2 == 0:
    for i in range(1,w):
        ass = min(ass,abs(h*i-(w-i)*h//2))
else:
    for i in range(1,w):
        ass = min(ass,max(abs(h*i-(h-1)*(w-i)//2),abs(h*i-(h+1)*(w-i)//2),w-i))

if w % 2 == 0:
    for i in range(1,h):
        ass = min(ass,abs(w*i-(h-i)*w//2))
else:
    for i in range(1,h):
        ass = min(ass,max(abs(w*i-(w-1)*(h-i)//2),abs(w*i-(w+1)*(h-i)//2),h-i))
print(ass)

Submission status: Accepted

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

if h%3==0 or w%3==0:
    print("0")
    exit()
#print(h*w)
ans=10**100**2
    #hが大きい方とみなす
if h<w:
    comp=h
    h=w
    w=comp
ans=min(ans,(h//3+1)*w-h//3*w)
#print(ans)
#print(h*w)
for i in range(1,w):
    green = h*i 
    red   = (h//2) * (w-i)
    blue  = h*w-red-green#三等分に分ける
    #print(green,red,blue)
    ma=max(green,red,blue)#一番大きい長方形
    mi=min(green,red,blue)#一番小さい長方形
    #print(green,red,blue,ma-mi)
   
    ans=min(ans,ma-mi)
comp=w
w=h
h=comp
for i in range(1,w):
    green = h*i 
    red   = (h//2) * (w-i)
    blue  = h*w-red-green#三等分に分ける
    ma=max(green,red,blue)#一番大きい長方形
    mi=min(green,red,blue)#一番小さい長方形
    #print(green,red,blue,ma-mi)
   
    ans=min(ans,ma-mi)

print(ans)

Submission status: Accepted

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

ans=float('inf')
for h in range(1,H+1):
  div1,div2=h*W,(H-h)*(W//2)
  div3=H*W - (div1+div2)
  divs=[div1,div2,div3]
  ans=min(ans,max(divs)-min(divs))
  div1,div2=h*W,((H-h)//2)*W
  div3=H*W - (div1+div2)
  divs=[div1,div2,div3]
  ans=min(ans,max(divs)-min(divs))
H,W=W,H
for h in range(1,H+1):
  div1,div2=h*W,(H-h)*(W//2)
  div3=H*W - (div1+div2)
  divs=[div1,div2,div3]
  ans=min(ans,max(divs)-min(divs))
  div1,div2=h*W,((H-h)//2)*W
  div3=H*W - (div1+div2)
  divs=[div1,div2,div3]
  ans=min(ans,max(divs)-min(divs))
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
 
res = min(H, W)
for h in range(H // 3, H // 3 + 3):
    w = W // 2
    s1 = h*W
    s2 = (H-h)*w
    s3 = (H-h)*(W-w)
    res = min(res, max(s1,s2,s3) - min(s1,s2,s3))
for w in range(W // 3, W // 3 + 3):
    h = H // 2
    s1 = w*H
    s2 = (W-w)*h
    s3 = (W-w)*(H-h)
    res = min(res, max(s1,s2,s3) - min(s1,s2,s3))
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    H,W = map(int,input().split())
    if (H%3 != 0 and W%3 != 0):
        ans = min(H,W)
        a = H//3
        b = (H-a)*(W//2)
        c = (H-a)*(-(-W//2))
        d = max(a*W,b,c)-min(a*W,b,c)
        a1 = a+1
        b1 = (H-a1)*(W//2)
        c1 = (H-a1)*(-(-W//2))
        d1 = max(a1*W,b1,c1)-min(a1*W,b1,c1)
        s = W//3
        t = (W-s)*(H//2)
        u = (W-s)*(-(-H//2))
        v = max(s*H,t,u)-min(s*H,t,u)
        s1 = s+1
        t1 = (W-s1)*(H//2)
        u1 = (W-s1)*(-(-H//2))
        v1 = max(s1*H,t1,u1)-min(s1*H,t1,u1)
        ans = min(ans,d,d1,v,v1)
        print(ans)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if (H*W)%3==0:
  ret=0
else:
  ret=min(H,W)
  S=[0]*3
  for h in range(1,H):
    S=[(W//2)*h, (W-W//2)*h, W*(H-h)]
    ret=min(ret,max(S)-min(S))
  for w in range(1,W):
    S=[(H//2)*w, (H-H//2)*w, H*(W-w)]
    ret=min(ret,max(S)-min(S))
print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = H * W
area = H * W
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    for i in range(1, H):
        kari = W * i
        if (H - i) % 2 == 0 or W % 2 == 0:
            kari_2 = (area - kari) // 2
            ans = min(ans, abs(kari-kari_2))
        else:
            kari_2 = (W // 2 + 1) * (H-i)
            kari_3 = (W // 2) * (H-i)
            ans = min(ans, max(kari, kari_2, kari_3)-min(kari, kari_2, kari_3))
    for j in range(1, W):
        kari = H * j
        if (W - j) % 2 == 0 or H % 2 == 0:
            kari_2 = (area - kari) // 2
            ans = min(ans, abs(kari-kari_2))
        else:

            kari_2 = (H // 2 + 1) * (W-j)
            kari_3 = (H // 2) * (W-j)
            ans = min(ans, max(kari, kari_2, kari_3)-min(kari, kari_2, kari_3))
    ans = min(ans, W, H)

    print(ans)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
a=10**10
S=H*W
s=[None]*3
for i in range(W):
    s[0]=H*i
    s[1]=(W-i)//2*H
    s[2]=S-s[0]-s[1]
    a=min(a,max(s)-min(s))
    s[1]=H//2*(W-i)
    s[2]=S-s[0]-s[1]
    a=min(a,max(s)-min(s))
for i in range(H):
    s[0]=W*i
    s[1]=(H-i)//2*W
    s[2]=S-s[0]-s[1]
    a=min(a,max(s)-min(s))
    s[1]=W//2*(H-i)
    s[2]=S-s[0]-s[1]
    a=min(a,max(s)-min(s))
print(a)

Submission status: Accepted

Solution code:
def areadifference(h , w):
    ans = 0
    count1 = 10000000000
    count2 = 10000000000
    if h % 3 == 0 or w % 3 == 0:
        return ans

    for i in range(1 , h + 1):
        hcount = max( i * w , (((h - i)//2) * w) , ((-(-(h - i)//2)) * w)) - min( i * w , (((h - i)//2) * w) , ((-(-(h - i)//2)) * w))
        wcount = max( i * w , ((h - i) * (w//2)) , ((h - i) * (-(-w//2)))) - min( i * w , ((h - i) * (w//2)) , ((h - i) * (-(-w//2))))
        count1 = min(count1 , hcount , wcount)

    for i in range(1 , w + 1):
        hcount = max( i * h , (((w - i)//2) * h) , ((-(-(w - i)//2)) * h)) - min( i * h , (((w - i)//2) * h) , ((-(-(w - i)//2)) * h))
        wcount = max( i * h , ((w - i) * (h//2)) , ((w - i) * (-(-h//2)))) - min( i * h , ((w - i) * (h//2)) , ((w - i) * (-(-h//2))))
        count2 = min(count2 , hcount , wcount)

    ans = min(count1 , count2)

    return ans

def main():
    h , w = map(int , input().split())
    print(areadifference(h , w))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**9
for i in range(1,w):
  ans=min(max(abs(i*h-h//2*(w-i)),abs(i*h-(h+1)//2*(w-i)),((h+1)//2-h//2)*(w-i)),ans)
for i in range(1,h):
  ans=min(max(abs(i*w-w//2*(h-i)),abs(i*w-(w+1)//2*(h-i)),((w+1)//2-w//2)*(h-i)),ans)
if h%3==0 or w%3==0:
  ans=0
else:
  ans=min(ans,h,w)
print(ans)

Submission status: Accepted

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

if H%3!=0 and W%3!=0:
  a=min(H,W)
else:
  print(0)
  exit()
b=H*W
for i in range(1,H):
  x=W*i
  if W%2==0:
    y=(H*W-x)//2
    z=y
  else:
    y=((H*W-x)+(H-i))//2
    z=y-(H-i)
  A=max(x,y,z)-min(x,y,z)
  b=min(A,b)

c=H*W
for i in range(1,W):
  x=H*i
  if H%2==0:
    y=(H*W-x)//2
    z=y
  else:
    y=((H*W-x)+(W-i))//2
    z=y-(W-i)
  B=max(x,y,z)-min(x,y,z)
  c=min(B,c)
print(min(a,b,c))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
def row_cut(p,q):
    res = 10**5
    for i in range(p):
        a = i * q
        b = ((p - i) // 2) * q
        c = (p * q) - a - b
        res = min(res, max(a,b,c) - min(a,b,c))
    return res 
def row_column_cut(p,q):
    res = 10**5
    for i in range(p):
        a = i * q
        b = (q // 2) * (p - i)
        c = (p * q) - a - b
        res = min(res, max(a,b,c) - min(a,b,c))
    return res
cand = [row_cut(h,w), row_cut(w,h), row_column_cut(w,h), row_column_cut(h,w)]
print(min(cand))

Submission status: Accepted

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

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

cand = []
for i in range(1, H+1):
    s_1 = i*W
    s_2_hor = (H-i)//2*W
    s_3_hor = (H-(i+(H-i)//2))*W
    s_2_ver = (H-i)*(W//2)
    s_3_ver = (H-i)*(W-W//2)
    ans_hor = abs(max(s_1, s_2_hor, s_3_hor) - min(s_1, s_2_hor, s_3_hor))
    ans_ver = abs(max(s_1, s_2_ver, s_3_ver) - min(s_1, s_2_ver, s_3_ver))
    cand.append(ans_hor)
    cand.append(ans_ver)

H, W = W, H
for i in range(1, H+1):
    s_1 = i*W
    s_2_hor = (H-i)//2*W
    s_3_hor = (H-(i+(H-i)//2))*W
    s_2_ver = (H-i)*(W//2)
    s_3_ver = (H-i)*(W-W//2)
    ans_hor = abs(max(s_1, s_2_hor, s_3_hor) - min(s_1, s_2_hor, s_3_hor))
    ans_ver = abs(max(s_1, s_2_ver, s_3_ver) - min(s_1, s_2_ver, s_3_ver))
    cand.append(ans_hor)
    cand.append(ans_ver)


print(min(cand))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
#l = sorted([int(input()) for i in range(N)],reverse=True)
def three(h,w):
    ans = h*w
    for i in range(h//3,h//3+2):
        A = w*i
        B = w*((h-i)//2)
        C = w*((h-i+1)//2)
        ans = min(ans,max(A,B,C)-min(A,B,C))
    return ans
def onetwo(h,w):
    ans = h*w
    for i in range(h//3,h//3+2):
        A = w*i
        B = (h-i)*(w//2)
        C = (h-i)*((w+1)//2)
        ans = min(ans,max(A,B,C)-min(A,B,C))
    return ans
print(min(three(H,W),three(W,H),onetwo(H,W),onetwo(W,H)))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
#l = sorted([int(input()) for i in range(N)],reverse=True)
def three(h,w):
    ans = h*w
    for i in range(1,h):
        A = w*i
        B = w*((h-i)//2)
        C = w*((h-i+1)//2)
        ans = min(ans,max(A,B,C)-min(A,B,C))
    return ans
def onetwo(h,w):
    ans = h*w
    for i in range(1,h):
        A = w*i
        B = (h-i)*(w//2)
        C = (h-i)*((w+1)//2)
        ans = min(ans,max(A,B,C)-min(A,B,C))
    return ans
print(min(three(H,W),three(W,H),onetwo(H,W),onetwo(W,H)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]

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

    if H % 2 == 0 and W % 2 == 0:
        print(min(H, W) // 2)
        return

    ans = min(H, W)
    ans2 = float("inf")
    for i in range(1, H // 2 + 2):
        a = i * W
        bc = H * W - a
        b = (W // 2) * (H - i)
        c = bc - b
        ma = max(a, b, c)
        mi = min(a, b, c)
        ans2 = min(ans2, ma - mi)

    for i in range(1, W // 2 + 2):
        a = i * H
        bc = H * W - a
        b = (H // 2) * (W - i)
        c = bc - b
        ma = max(a, b, c)
        mi = min(a, b, c)
        ans2 = min(ans2, ma - mi)

    print(min(ans, ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def calc(h,w):
    minv = 2 ** 32
    for i in range(1, h):
        s1 = i * w
        s2 = ((h-i) // 2) * w
        s3 = (h - i - ((h-i) // 2)) * w
        lmin = max(s1, s2, s3) - min(s1, s2, s3)
        minv = min(minv, lmin)

        s2v = (h - i) * (w // 2)
        s3v = (h - i) * (w - w // 2)
        minv = min(minv, max(s1, s2v, s3v) - min(s1, s2v, s3v))
    return minv

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

Submission status: Accepted

Solution code:
#C
H,W = map(int,input().split())
whole = H*W

MIN = float("inf")
for h in range(H):
    s1 = (h+1)*W
    s2 = W*((H-(h+1))//2)
    s3 = whole - (s1+s2)
    s4 = (H-(h+1))*(W//2)
    s5 = whole - (s1+s4)
    kari1 = max({s1,s2,s3})-min({s1,s2,s3})
    kari2 = max({s1,s4,s5})-min({s1,s4,s5})
    MIN = min({kari1,kari2,MIN})
for w in range(W):
    s1 = (w+1)*H
    s2 = H*((W-(w+1))//2)
    s3 = whole - (s1+s2)
    s4 = (W-(w+1))*(H//2)
    s5 = whole - (s1+s4)
    kari1 = max({s1,s2,s3})-min({s1,s2,s3})
    kari2 = max({s1,s4,s5})-min({s1,s4,s5})
    MIN = min({kari1,kari2,MIN})
    
print(MIN)

Submission status: Accepted

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

hwList = []
hhList = []
whList = []
wwList = []
for i in range(1,h+1):
  sa = i*w
  sb = (h-i)*(w//2)
  sc = (h-i)*(w-(w//2))
  hwList.append(max([sa,sb,sc])-min([sa,sb,sc]))
  sb = (h-i)//2*(w)
  sc = ((h-i)-((h-i)//2))*(w)
  hhList.append(max([sa,sb,sc])-min([sa,sb,sc]))
for i in range(1,w+1):
  sa = i*h
  sb = (w-i)*(h//2)
  sc = (w-i)*(h-(h//2))
  whList.append(max([sa,sb,sc])-min([sa,sb,sc]))
  sb = (w-i)//2*(h)
  sc = ((w-i)-((w-i)//2))*(h)
  wwList.append(max([sa,sb,sc])-min([sa,sb,sc]))

print(min([min(hwList),min(hhList),min(whList),min(wwList)]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

ans = INF

for h in range(1, H+1):
	S1 = h*W
	S2 = (H-h)*(W//2)
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

H, W = W, H

for h in range(1, H+1):
	S1 = h*W
	S2 = (H-h)*(W//2)
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

ans = INF

for h in range(1, H+1):
	S1 = h*W
	w = W//2
	S2 = (H-h)*w
	S3 = (H-h)*(W-w)
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

H, W = W, H

for h in range(1, H+1):
	S1 = h*W
	w = W//2
	S2 = (H-h)*w
	S3 = (H-h)*(W-w)
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

print(ans)

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)

for i in range(2):
    tmp = h//3 + i
    p = [0]*3
    p[0] = tmp*w
    p[1],p[2] = (h-tmp)*(w//2), (h-tmp)*((w+1)//2)
    p.sort()
    ans = min(ans,p[2]-p[0])

    tmp = w//3 + i
    p = [0]*3
    p[0] = tmp*h
    p[1],p[2] = (w-tmp)*(h//2), (w-tmp)*((h+1)//2)
    p.sort()
    ans = min(ans,p[2]-p[0])
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = min(H, W)
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    for h in range(1, H):
        s1 = h * W
        s2 = (H - h) * (W // 2)
        s3 = (H - h) * ((W + 1)// 2)
        ans = min(ans, max(s1,s2,s3) - min(s1,s2,s3))
    for w in range(1, W):
        s1 = w * H
        s2 = (W - w) * (H // 2)
        s3 = (W - w) * ((H + 1)// 2)
        ans = min(ans, max(s1,s2,s3) - min(s1,s2,s3))
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)

e=[0]*2
e[0]=max(H,W)
e[1]=min(H,W)

ans=H*W
for i in range(2):
  a=e[i]
  b=e[i^1]
  # aを3等分で切ろうとして、切り捨てるか切り上げるかの二通り
  a2=[0]*2
  a2[0]=a//3
  a2[1]=a//3+1
  for j in range(2):
    area=[0]*3
    if a2[j]==0:
      continue
    area[0]=a2[j]*b
    # 一つ目の面積が決まり
    a_rest=a-a2[j]
    # 残りのa_rest * bを, どちらから切るか
    c=[0]*2
    c[0]=max(a_rest,b)
    c[1]=min(a_rest,b)
    for k in range(2):
      p=c[k]
      q=c[k^1]
      if p%2==0:
        area[1]=area[2]=p*q//2
      else:
        # pを二等分しようとして、切り捨てるか切り上げるかの二通り
        p2=[0]*2
        p2[0]=p//2
        p2[1]=p//2+1
        for u in range(2):
          if p2[u]==0:
            continue
          area[1]=p2[u]*q
          area[2]=(p-p2[u])*q
      if area[0]<=0 or area[1]<=0 or area[2]<=0:
        continue
      diff=max(area)-min(area)
      if ans>diff:
        ans=diff
print(ans)

Submission status: Accepted

Solution code:
W,H = map(int,input().split())
ans = 10**30
for i in range(1,W):
    a = H*i
    w = W - i
    b = max((w//2)*H,w*(H//2))
    c = w*H - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
for i in range(1,H):
    a = W*i
    h = H - i
    b = max((W//2)*h,W*(h//2))
    c = h*W - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
if h%3 == 0:
    m1 = 0
else:
    m1 = w
if w%3 == 0:
    m2 = 0
else:
    m2 = h
m3 = m4 = h*w
for i in range(1,h):
    m3 = min(m3, max(i*w, (h-i)*(w//2), (h-i)*(w-w//2)) - min(i*w, (h-i)*(w//2), (h-i)*(w-w//2)))
for i in range(1,w):
    m4 = min(m4, max(i*h, (w-i)*(h//2), (w-i)*(h-h//2)) - min(i*h, (w-i)*(h//2), (w-i)*(h-h//2)))
print(min(m1, m2, m3, m4))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

def calc(main,sub):
    if main%3==1:
        a=main//3
    else:
        a=main//3+1
    b=sub//2
    temp=[a*sub,(main-a)*b,(main-a)*(sub-b)]
    
    return max(temp)-min(temp)
        

if H%3==0 or W%3==0:
    print(0)
else:
    print(min(calc(H,W),calc(W,H),H,W))

Submission status: Accepted

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

ans = h*w
for i in range(1,h):
  a = w*i
  b1 = w*((h-i+1)//2)
  c1 = w*((h-i)//2)
  #print("{} {} {}".format(a,b1,c1))
  ans = min(max(a,b1,c1)-min(a,b1,c1),ans)
  b2 = (h-i)*((w+1)//2)
  c2 = (h-i)*(w//2)
  #print("{} {} {}".format(a,b2,c2))
  ans = min(max(a,b2,c2)-min(a,b2,c2),ans)
for i in range(1,w):
  a = h*i
  b1 = h*((w-i+1)//2)
  c1 = h*((w-i)//2)
  #print("{} {} {}".format(a,b1,c1))
  ans = min(max(a,b1,c1)-min(a,b1,c1),ans)
  b2 = (w-i)*((h+1)//2)
  c2 = (w-i)*(h//2)
  #print("{} {} {}".format(a,b2,c2))
  ans = min(max(a,b2,c2)-min(a,b2,c2),ans)
print(ans)

Submission status: Accepted

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


def sdif(h1,w1,h2,w2,h3,w3):
    s1=h1*w1
    s2=h2*w2
    s3=h3*w3
    return max(abs(s1-s2),abs(s2-s3),abs(s3-s1))

if h % 3==0 or w% 3== 0:
    print(0)
else:
    h1=h//3
    w1=w
    h2=h-h1
    w2=w//2
    h3=h2
    w3=w-w2
    r1=sdif(h1,w1,h2,w2,h3,w3)
    h1=h//3+1
    w1=w
    h2=h-h1
    w2=w//2
    h3=h2
    w3=w-w2
    r2=sdif(h1,w1,h2,w2,h3,w3)
    w1=w//3
    h1=h
    w2=w-w1
    h2=h//2
    w3=w2
    h3=h-h2
    r3=sdif(h1,w1,h2,w2,h3,w3)
    w1=w//3+1
    h1=h
    w2=w-w1
    h2=h//2
    w3=w2
    h3=h-h2
    r4=sdif(h1,w1,h2,w2,h3,w3)
    print(min(h,w,r1,r2,r3,r4))

Submission status: Accepted

Solution code:
def parallel(h, w):
    q, r = divmod(h, 3)
    if r == 0:
        return 0
    else:
        return w


def t(h, w):
    ret = h * w

    q = h // 3
    c = w // 2
    for r in range(q, q + 2):
        set_ = (r * w, (h - r) * c, (h - r) * (w - c))
        ret = min(ret, max(set_) - min(set_))

    return ret


def main():
    h, w = map(int, input().split())
    print(min(parallel(h, w), parallel(w, h), t(h, w), t(w, h)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:    # 3の倍数だったら最小値は0
    print(0)
    exit()

answer = float('inf')

h = 1
for _ in range(H):
    a = h * W
    b = (H-h) * (W // 2)
    c = H * W - a - b
    MAX = max([a, b, c])
    MIN = min([a, b, c])
    if MAX - MIN <= answer:
        answer = MAX - MIN
    h += 1

w = 1
for _ in range(W):
    a = w * H
    b = (W-w) * (H // 2)
    c = H * W - a - b
    MAX = max([a, b, c])
    MIN = min([a, b, c])
    if MAX - MIN <= answer:
        answer = MAX - MIN
    w += 1

a = W // 3
b = (W - a) // 2
c = W - a - ((W - a) // 2)
a *= H
b *= H
c *= H
MAX = max([a, b, c])
MIN = min([a, b, c])
if MAX - MIN <= answer:
    answer = MAX - MIN

a = H // 3
b = (H - a) // 2
c = H - a - ((H - a) // 2)
a *= W
b *= W
c *= W
MAX = max([a, b, c])
MIN = min([a, b, c])
if MAX - MIN <= answer:
    answer = MAX - MIN

print(answer)

Submission status: Accepted

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

S = H*W
ans = 10**10

hs = H//2
ws = W//2

for h in range(1,hs+1):
    a = h*W
    if (H-h)%2 == 0 or W%2 == 0:
        b = (S-a)//2
    else:
        b = min(H-h,W)*(max(H-h,W)//2)
    c = S-a-b
    d = max(a,b,c)-min(a,b,c)
    ans = min(ans,d)

for w in range(1,ws+1):
    a = H*w
    if (W-w)%2 == 0 or H%2 == 0:
        b = (S-a)//2
    else:
        b = min(W-w,H)*(max(W-w,H)//2)
    c = S-a-b
    d = max(a,b,c)-min(a,b,c)
    ans = min(ans,d)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
    exit()
mn=float("inf")
for i in range(1,h):
    a=w*(h-i)
    b=i*-(-w//2)
    c=i*(w//2)
    dai=max(a,b,c)
    syo=min(a,b,c)
    #print(a,b,c,i)
    mn=min(mn,dai-syo)
for i in range(1,w):
    a=h*(w-i)
    b=i*-(-h//2)
    c=i*(h//2)
    dai=max(a,b,c)
    syo=min(a,b,c)
    #print(a,b,c,i)
    mn=min(mn,dai-syo)
mn=min(mn,h,w)
print(mn)

Submission status: Accepted

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

ans = H * W
for ha in range(1, H):
    a = ha * W

    hb = (H - ha) // 2

    b = hb * W
    c = H * W - a - b

    ans = min(ans, max(a, b, c) - min(a, b, c))

    wb = W // 2
    b = (H - ha) * wb
    c = H * W - a - b

    ans = min(ans, max(a, b, c) - min(a, b, c))

for wa in range(1, W):
    a = H * wa

    wb = (W - wa) // 2

    b = H * wb
    c = H * W - a - b

    ans = min(ans, max(a, b, c) - min(a, b, c))

    hb = H // 2
    b = (W - wa) * hb
    c = H * W - a - b

    ans = min(ans, max(a, b, c) - min(a, b, c))

print(ans)

Submission status: Accepted

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

# 一発目を横に切る
tmp = h // 3
a = tmp * w
b = (h-tmp) // 2 * w
c = h*w - a - b
ans = max([a, b, c]) - min([a, b, c])

tmp = (h+2) // 3
a = tmp * w
b = (h-tmp) // 2 * w
c = h*w - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

tmp = h // 3
a = tmp * w
b = (h-tmp) * (w//2)
c = h*w - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

tmp = (h+2) // 3
a = tmp * w
b = (h-tmp) * (w//2)
c = h*w - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

# 一発目を縦に切る
tmp = w // 3
a = tmp * h
b = (w-tmp) // 2 * h
c = w*h - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

tmp = (w+2) // 3
a = tmp * h
b = (w-tmp) // 2 * h
c = w*h - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

tmp = w // 3
a = tmp * h
b = (w-tmp) * (h//2)
c = w*h - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

tmp = (w+2) // 3
a = tmp * h
b = (w-tmp) * (h//2)
c = w*h - a - b
ans = min(ans, max([a, b, c]) - min([a, b, c]))

print(ans)

Submission status: Accepted

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

ans = 10**10

for _ in range(2):
    for h in range(1, H):
        a = h * W
        b = (H-h)//2 * W
        c = (H - h - (H-h)//2) * W
        d = max(a,b,c) - min(a,b,c)
        ans = min(ans, d)
        b = (H-h) * (W//2)
        c = (H-h) * (W-W//2)
        d = max(a,b,c) - min(a,b,c)
        ans = min(ans, d)
    H, W = W, H

print(ans)