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

Solution (Python):
H,W = map(int,input().split())
if H%3 == 0 or W%3 == 0:
    print(0)
else:
    ans = min(H,W)
    if W%2 == 0:
        ans = min(ans,W//2)
    else:
        if H%3 == 1:
            ans = min(ans,(W+1)//2+(H-1)//3)
        else:
            ans = min(ans,(W+1)//2+(H-2)//3)
    if H%2 == 0:
        ans = min(ans,H//2)
    else:
        if W%3 == 1:
            ans = min(ans,(H+1)//2+(W-1)//3)
        else:
            ans = min(ans,(H+1)//2+(W-2)//3)
    print(ans)

Solution (Python):
a, b = map(int, input().split())
if a % 3 == 0 or b % 3 == 0:
  print(0)
  exit()

ds = min(a, b)

s0 = (a//3) * b
s1 = (a - (a//3)) * (b//2)
s2 = (a - (a//3)) * (b - (b//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (a//3 + 1) * b
s1 = (a - (a//3) - 1) * (b//2)
s2 = (a - (a//3) - 1) * (b - (b//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (b//3) * a
s1 = (b - (b//3)) * (a//2)
s2 = (b - (b//3)) * (a - (a//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

s0 = (b//3 + 1) * a
s1 = (b - (b//3) - 1) * (a//2)
s2 = (b - (b//3) - 1) * (a - (a//2))
if 0 not in (s0, s1, s2):
  ds = min(ds, max(s0, s1, s2) - min(s0, s1, s2))

print(ds)

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

def solve(H, W):
  if H % 3 == 0 or W % 3 == 0:
    return 0  
  else:
    ans = 1e20
    for i in range(max(W//3-1, 1), min(W//3+2, W)):
      a = i
      b = W - a
      for i in range(max(H//2-1, 1), min(H//2+2, H)):
        c = i
        d = H - c
        S = [a*H, b*c, b*d]
        ans = min(ans, max(S)-min(S))
      for i in range(max(b//2-1, 1), min(b//2+2, b)):
        c = i
        d = b - c
        S = [a*H, c*H, d*H]
        ans = min(ans, max(S)-min(S))
  return ans

print(min(solve(H, W), solve(W, H)))

Solution (Python):
def f(a, b, c):
    return max(a, b, c) - min(a, b, c)


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

Solution (Python):


h,w=map(int,input().split())

if (h*w)%3==0:
    print(0)
    exit()


def solve(s):
    global h,w
    
    cnt=float('inf')
    if s==h:
        H,W=w,h
    else:
        H,W=h,w
    for i in range(1,s+1):
        a=i*H
        rest=H*(w-i)
        if rest%2==0:
            b=c=rest//2
        else:
            ww=W-i
            hh=H
            bb=max(ww,hh)//2
            cc=bb+1
            b=min(ww,hh)*bb
            c=min(ww,hh)*cc
        cnt=min((max(a,b,c)-min(a,b,c)),cnt)

    return cnt


ans=min(solve(h),solve(w))
print(ans)

Solution (Python):
H, W = map(int, input().split())
if H%3 == 0 or H%3 == 0:
    ans = 0
else:
    ansl = [H] + [W] + [H*W] * 2
    if W%2 == 0:
        for i in range(1, H):
            tmp = abs(i * W - (H-i) * W // 2)
            if ansl[2] > tmp:
                ansl[2] = tmp
    else:
        for i in range(1, H):
            S1 = W * i
            S2 = (H-i) * (W//2)
            S3 = H*W - S1 - S2
            tmp = max(S1, S2, S3) - min(S1, S2, S3)
            if ansl[2] > tmp:
                ansl[2] = tmp
    if H == W:
        ansl[3] = ansl[2]
    elif H%2 == 0:
        for i in range(1, W):
            tmp = abs(i * H - (W-i) * H // 2)
            if ansl[3] > tmp:
                ansl[3] = tmp
    else:
        for i in range(1, W):
            S1 = H * i
            S2 = (W-i) * (H//2)
            S3 = H*W - S1 - S2
            tmp = max(S1, S2, S3) - min(S1, S2, S3)
            if ansl[3] > tmp:
                ansl[3] = tmp
    ans = min(ansl)
print(ans)

Solution (Python):
h,w=map(int, input().split())
a=[]
b=[]
c=[]
d=[]

if h%3==0 or w%3==0:
    print(0)
    exit()

a.append(h//3*w)
a.append(w//2*(h-h//3))
a.append((w-w//2)*(h-h//3))
ans1=max(a)-min(a)

b.append((h//3+1)*w)
b.append(w//2*(h-(h//3+1)))
b.append((w-w//2)*(h-(h//3+1)))
ans2=max(b)-min(b)

c.append(w//3*h)
c.append(h//2*(w-w//3))
c.append((h-h//2)*(w-w//3))
ans3=max(c)-min(c)

d.append((w//3+1)*h)
d.append(h//2*(w-(w//3+1)))
d.append((h-h//2)*(w-(w//3+1)))
ans4=max(d)-min(d)

print(min(ans1,ans2,ans3,ans4,min(h,w)))

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

ans_list = list()


for h1 in {h // 3, h // 3 + 1}:
    h_rest = h - h1
    if h1 <= 0 or h_rest <= 0:
        continue
    
    h2 = h_rest >> 1
    if h2 != 0:
        S = [h1 * w, h2 * w, (h_rest - h2) * w]
        ans_list.append(max(S) - min(S))
        

    
    w2 = w >> 1
    if w2 != 0:
        S = [h1 * w, h_rest * w2, h_rest * (w - w2)]
        
        ans_list.append(max(S) - min(S))


for w1 in {w // 3, w // 3 + 1}:
    w_rest = w - w1
    if w1 <= 0 or w_rest <= 0:
        continue
    
    w2 = w_rest >> 1
    if w2 != 0:
        S = [h * w1, h * w2, h * (w_rest - w2)]
        ans_list.append(max(S) - min(S))
        
    
    h2 = h >> 1
    if h2 != 0:
        S = [h * w1, h2 * w_rest, (h - h2) * w_rest]
        ans_list.append(max(S) - min(S))
        



print(min(ans_list))

Solution (Python):
def calc(h, w):
    w_1_1 = w // 3
    w_1_2 = w_1_1 + 1

    ans = inf
    for w_1 in w_1_1, w_1_2:
        s_1 = w_1 * h

        
        w_2 = (w - w_1) // 2
        s_2 = w_2 * h

        w_3 = w - w_1 - w_2
        s_3 = w_3 * h

        ss = [s_1, s_2, s_3]
        
        ans = min(ans, max(ss) - min(ss))

        
        h_2 = h // 2
        s_2 = h_2 * (w - w_1)

        h_3 = h - h_2
        s_3 = h_3 * (w - w_1)

        ss = [s_1, s_2, s_3]
        
        ans = min(ans, max(ss) - min(ss))

    return ans


inf = float('inf')

h, w = map(int, input().split())

a = calc(h, w)
b = calc(w, h)
print(min(a, b))

Solution (Python):
h,w=map(int,input().split());print(min(h//2+w//3+1,h//3+w//2+1,h*(h%3>0)//(2-h%2),w*(w%3>0)//(2-w%2)))

Solution (Python):
M=min
def f(x,y):
	m=x*(x%3>0)
	for i in(0,1):
		d=x//3+i;e=x-d;l=[d*y,y//2*e,-~y//2*e];m=M(m,max(l)-M(l))
	return m
h,w=map(int,input().split());print(M(f(h,w),f(w,h)))

Solution (Python):
H, W = map(int, input().split())
pattern = [H//2 + W//3 + 1, W//3 + H//2 + 1, H, W]
if H % 3 == 0 or W % 3 == 0:
    pattern += [0]
if H % 2 == 0:
    pattern += [H//2]
if W % 2 == 0:
    pattern += [W//2]
print(min(pattern))

Solution (Python):
h,w=map(int,input().split())
candidate=[0]*4
if h*w%3==0:
	print(0)
	exit()

def solve(a,b,k):
	candidate[k]=a
	cnd=float('inf')
	for i in range(a+1):
		c1=b*i
		c2=(a-i)*(b//2)
		c3=(a-i)*(b-b//2)
		cnd=min(cnd,max(c1,c2,c3)-min(c1,c2,c3))
	candidate[k+1]=cnd

solve(h,w,0)
solve(w,h,2)
print(min(candidate))

Solution (Python):
H, W = map(int,input().split())
ans = float('inf')
for i in range(1, H):
    a = i*W
    if H-i == 1:
        d = 1*(W//2)
        e = H*W-a-d
        small = min(a,d,e)
        large = max(a,d,e)
        ans = min(ans, large-small)
    else:
        b = ((H-i)//2) * W
        c = H*W-a-b
        d = (H-i) * (W//2)
        e = H*W-a-d
        small1 = min(a,b,c)
        large1 = max(a,b,c)
        small2 = min(a,d,e)
        large2 = max(a,d,e)
        ans = min(ans, large1-small1, large2-small2)
for j in range(1, W):
    a = j*H
    if W-j == 1:
        d = 1*(H//2)
        e = H*W-a-d
        small = min(a,d,e)
        large = max(a,d,e)
        ans = min(ans, large-small)
    else:
        b = ((W-j)//2) * H
        c = H*W-a-b
        d = (W-j) * (H//2)
        e = H*W-a-d
        small1 = min(a,b,c)
        large1 = max(a,b,c)
        small2 = min(a,d,e)
        large2 = max(a,d,e)
        ans = min(ans, large1-small2, large2-small2)
print(ans)

Solution (Python):
H, W = list(map(int, input().split()))
ans = []


for i in range(1, H):
    area1 = W*i
    area2 = (H-i)//2*W
    area3 = (H-(H-i)//2-i)*W
    area4 = (H-i)*(W//2)
    area5 = (H-i)*(W-(W//2))
    if area1 != 0 or area2 != 0 or area3 !=0:
        ans.append(max(area1, area2, area3)-min(area1, area2, area3))
    if area1 != 0 or area4 != 0 or area5 !=0:
        ans.append(max(area1, area4, area5)-min(area1, area4, area5))


for i in range(1, W):
    area6 = H*i
    area7 = (W-i)//2*H
    area8 = (W-(W-i)//2-i)*H
    area9 = (W-i)*(H//2)
    area10 = (W-i)*(H-(H//2))
    if area6 != 0 or area7 != 0 or area8 !=0:
        ans.append(max(area6, area7, area8)-min(area6, area7, area8))
    if area6 != 0 or area9 != 0 or area10 !=0:
        ans.append(max(area6, area9, area10)-min(area6, area9, area10))

print(min(ans))

Solution (Python):


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

Ans = 99999999999999999

TDPAns = min((1 if H % 3 != 0 else 0) * W, (1 if W % 3 != 0 else 0) * H)

OTDPAns = Ans
TODPAns = Ans


for x in range(1, W + 1):
    width = W - x
    row_mass = x * H
    sub = Ans
    if H % 2 == 0:
        y = H // 2
        sub = max(row_mass, (width * y)) - min(row_mass, (width * y))
    else:
        y1 = (H // 2) + 1
        y2 = (H // 2)
        sub = max(row_mass, (width * y1), (width * y2)) - min(row_mass, (width * y1), (width * y2))

    OTDPAns = min(OTDPAns, sub)


for y in range(1, H + 1):
    height = H - y
    line_mass = height * W
    sub = Ans
    if W % 2 == 0:
        x = W // 2
        sub = max(line_mass, x * y) - min(line_mass, x * y)
    else:
        x1 = (W // 2) + 1
        x2 = (W // 2)
        sub = max(line_mass, x1 * y, x2 * y) - min(line_mass, x1 * y, x2 * y)
    TODPAns = min(TODPAns, sub)


print(min(TDPAns, OTDPAns, TODPAns))

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
    
yoko = h // 3

sa = 10**100

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

tmp = h
h = w
w = tmp

yoko = h // 3

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

        
print(min(sa,h,w))

Solution (Python):
import math

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

ans=H*W
for i in range(1,H):
	s=i*W
	h=H-i
	t1=(h//2)*W
	t2=math.ceil(h/2)*W
	if all([s,t1,t2]):
		ans=min(ans, max(s,t1,t2)-min(s,t1,t2))
	
	t1=(W//2)*h
	t2=math.ceil(W/2)*h
	if all([s,t1,t2]):
		ans=min(ans, max(s,t1,t2)-min(s,t1,t2))

for i in range(1,W):
	s=i*H
	w=W-i
	t1=(w//2)*H
	t2=math.ceil(w/2)*H
	if all([s,t1,t2]):
		ans=min(ans, max(s,t1,t2)-min(s,t1,t2))
	
	t1=(H//2)*w
	t2=math.ceil(H/2)*w
	if all([s,t1,t2]):
		ans=min(ans, max(s,t1,t2)-min(s,t1,t2))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

h, w = sorted(map(int, input().split()))
if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    c_1 = ((w // 3 + 1) * h) - ((w - 1 - w // 3) * (h // 2))
    c_2 = ((w - w // 3) * (h - h // 2)) - (w // 3 * h)
    c_3 = h
    c_4 = ((h // 3 + 1) * w) - ((h - 1 - h // 3) * (w // 2))
    c_5 = ((h - h // 3) * (w - w // 2)) - (h // 3 * w)
    ans = min(c_1, c_2, c_3, c_4, c_5)
print(ans)

Solution (Python):
H,W = map(int, input().strip().split(' '))

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

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

Solution (Python):
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

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

bx = min(H, W) // 2
cx = min(H, W) - bx
ans = 10 ** 18
for i in range(1, max(H, W)):
    a = min(H, W) * i

    b = (max(H, W) - i) * bx
    c = (max(H, W) - i) * cx

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

bx = max(H, W) // 2
cx = max(H, W) - bx
for i in range(1, min(H, W)):
    a = max(H, W) * i

    b = (min(H, W) - i) * bx
    c = (min(H, W) - i) * cx

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

aa = H // 3
bb = (H - aa) // 2
cc = H - aa - bb
ans = min(ans, (max(aa, bb, cc) - min(aa, bb, cc)) * W)

aa = W // 3
bb = (W - aa) // 2
cc = W - aa - bb
ans = min(ans, (max(aa, bb, cc) - min(aa, bb, cc)) * H)

print(ans)

Solution (Python):
h,w=map(int,input().split())
h3=h//3
h3a=h%3
w3=w//3
w3a=w%3

ans = min((((h3-(-h3a//2)))-h3)*w,  (((w3-(-w3a//2))-w3)*h))

h2 = h//2
w2 = w//2
h2a=h%2
w2a=w%2

ans=min(ans, abs((h3)*w-(w2+w2a)*(h-h3)), abs((h3-(-h3a//2))*w-w2*(h-(h3-(-h3a//2)))))
ans = min(ans, abs((w3)*h-(h2+h2a)*(w-w3)), abs((w3-(-w3a//2))*h-h2*(w-(w3-(-w3a//2)))))

print(ans)

Solution (Python):
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

h, w = na()
s = h * w
mid_h = h // 2
mid_w = w // 2
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ans = s
    for i in range(mid_w+1)[::-1]:
        s0 = h * i
        s1 = ((w - i) // 2) * h
        s2 = s - s0 - s1
        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))
        s1 = (w - i) * mid_h
        s2 = s - s0 - s1
        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))
    for i in range(mid_h+1)[::-1]:
        s0 = w * i
        s1 = ((h - i) // 2) * w
        s2 = s - s0 - s1
        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))
        s1 = (h - i) * mid_w
        s2 = s - s0 - s1
        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))
    print(ans)

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

anss = []

def vertical_twice(H,W):
    if W % 3 == 0:
        return 0
    else:
        return H

def vertical_horizontal(H,W):
    if W % 3 != 2:
        left_width = W//3
        left_area = H*left_width
        right_width = W - left_width
        if H % 2 == 0:
            right_upper_area = H//2*right_width
            right_lower_area = H//2*right_width

        else:
            right_upper_area = (H//2+1)*right_width
            right_lower_area = H//2*right_width

    
    if W % 3 == 2:
        left_width = W//3+1
        left_area = H*left_width
        right_width = W - left_width
        if H % 2 == 0:
            right_upper_area = H//2*right_width
            right_lower_area = H//2*right_width

        else:
            right_upper_area = (H//2+1)*right_width
            right_lower_area = H//2*right_width

    return (max([left_area,right_upper_area, right_lower_area])-
            min([left_area,right_upper_area, right_lower_area]))
            
anss.append(vertical_twice(H,W))
anss.append(vertical_twice(W,H))
anss.append(vertical_horizontal(H,W))
anss.append(vertical_horizontal(W,H))

print(min(anss))

Solution (Python):
import math
H,W = map(int,input().split())
ans = float('inf')
S = H*W
def minimum(x,y,z):
    S_max = max(x,y,z)
    S_min = min(x,y,z)
    return S_max-S_min
for h in range(1,H+1):
    A = h*W
    B = math.floor((H-h)/2) * W
    C = S-A-B
    ans = min(ans,minimum(A,B,C))
    
    B = (H-h)*math.floor(W/2)
    C = S-A-B
    ans = min(ans,minimum(A,B,C))

for w in range(1,W+1):
    A = H*w
    B = math.floor((W-w)/2) * H
    C = S-A-B
    ans = min(ans,minimum(A,B,C))

    B =(W-w)*math.floor(H/2)
    C = S-A-B
    ans =  min(ans,minimum(A,B,C)) 
print(ans)

Solution (Python):
h,w = sorted(list(map(int,input().split())))
if h % 3 == 0 or w % 3 == 0:
  ret = 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)
  ret = min(c1,c2,c3,c4,c5)
print(ret)

Solution (Python):
H, W = map(int, input().split())
s = (H*W)/3
counth = 0
while counth<s:
  counth += W
if abs(counth-s) > abs(counth-s-W):
  counth -= W
Mhs = counth
counth = counth//W
H1 = H-counth
ls = [Mhs, H1*(W//2), H*W-Mhs-H1*(W//2)]

ansh = [max(ls)-min(ls)]
ls = [Mhs, W*(H1//2), H*W-Mhs-W*(H1//2)]

ansh += [max(ls)-min(ls)]
ansh = min(ansh)
countw = 0
while countw<s:
  countw += H
if abs(countw-s) > abs(countw-s-H):
  countw -= H
Mws = countw
countw = countw//H
W1 = W-countw
ls = [Mws, W1*(H//2), H*W-Mws-W1*(H//2)]

answ = [max(ls)-min(ls)]
ls = [Mws, H*(W1//2), H*W-H*(W1//2)-Mws]
answ += [max(ls)-min(ls)]

answ = min(answ)
print(min(ansh, answ))

Solution (Python):
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    min_diff = h * w

    h1 = h // 2
    h2 = h - h1
    for w3 in range(w // 3, w // 3 + 2):
        s = [h * w3, h1 * (w - w3), h2 * (w - w3)]
        min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 2
    w2 = w - w1
    for h3 in range(h // 3, h // 3 + 2):
        s = [w * h3, w1 * (h - h3), w2 * (h - h3)]
        min_diff = min(min_diff, max(s) - min(s))

    h1 = h // 3
    h2 = (h - h1) // 2
    h3 = h - h1 - h2
    s = [w * h1, w * h2, w * h3]
    min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 3
    w2 = (w - w1) // 2
    w3 = w - w1 - w2
    s = [h * w1, h * w2, h * w3]
    min_diff = min(min_diff, max(s) - min(s))

    print(min_diff)

Solution (Python):
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    min_diff = h * w

    h1 = h // 2
    h2 = h - h1
    for w3 in range(w // 3, w // 3 + 3):
        s = [h * w3, h1 * (w - w3), h2 * (w - w3)]
        min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 2
    w2 = w - w1
    for h3 in range(h // 3, h // 3 + 3):
        s = [w * h3, w1 * (h - h3), w2 * (h - h3)]
        min_diff = min(min_diff, max(s) - min(s))

    h1 = h // 3
    h2 = (h - h1) // 2
    h3 = h - h1 - h2
    s = [w * h1, w * h2, w * h3]
    min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 3
    w2 = (w - w1) // 2
    w3 = w - w1 - w2
    s = [h * w1, h * w2, h * w3]
    min_diff = min(min_diff, max(s) - min(s))

    print(min_diff)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

def calc(h1, h2, W):
    
    a = h1 * W
    b = h2 * (W//2)
    c = h2 * ceil(W, 2)
    return max(abs(a-b), abs(b-c), abs(c-a))

ans = INF

h1 = H // 3
h2 = H - h1
ans = min(ans, calc(h1, h2, W))
h1 = ceil(H, 3)
h2 = H - h1
ans = min(ans, calc(h1, h2, W))


H, W = W, H
h1 = H // 3
h2 = H - h1
ans = min(ans, calc(h1, h2, W))
h1 = ceil(H, 3)
h2 = H - h1
ans = min(ans, calc(h1, h2, W))


ans = min(ans, abs(ceil(W, 3)*H-W//3*H))
ans = min(ans, abs(ceil(H, 3)*W-H//3*W))

print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

H, W = max(H, W), min(H, W)

a = H // 3
bc = H - a
ans1 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))
a = ceil(H, 3)
bc = H - a
ans2 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))

H, W = min(H, W), max(H, W)

a = H // 3
bc = H - a
ans3 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))
a = ceil(H, 3)
bc = H - a
ans4 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))

ans5 = abs(ceil(W, 3)*H-W//3*H)
ans6 = abs(ceil(H, 3)*W-H//3*W)

print(min(ans1, ans2, ans3, ans4, ans5, ans6))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

H, W = max(H, W), min(H, W)

a = H // 3
bc = H - a
ans1 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))
a = ceil(H, 3)
bc = H - a
ans2 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))

H, W = min(H, W), max(H, W)

a = H // 3
bc = H - a
ans3 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))
a = ceil(H, 3)
bc = H - a
ans4 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))

ans5 = abs(ceil(W, 3)*H-W//3*H)
ans6 = abs(ceil(H, 3)*W-H//3*W)

print(min(ans1, ans2, ans3, ans4, ans5, ans6))

Solution (Python):
H, W = map(int, input().split())
value = H * W








if W % 3 == 0:
  value = 0
else:
  value = H


if H % 3 == 0:
  value = 0
else:
  value = min(value, W)
  

if W % 3 != 0: 
  for i in range(3):
    w1 = W//3 - 1 + i
    s1 = H * w1
    w_amari = W - w1
    for j in range(3):
      h1 = H//2 - 1 + j
      s2 = h1 * w_amari
      s3 = H * W - s1 - s2
      value2 = max(s1,s2,s3) - min(s1,s2,s3)
      
      value = min(value, value2)

if H % 3 != 0: 
  for i in range(3):
    h1 = H//3 - 1 + i
    s1 = h1 * W
    h_amari = H - h1
    for j in range(3):
      w1 = W//2 - 1 + j
      s2 = h_amari * w1
      s3 = H * W - s1 - s2
      value3 = max(s1,s2,s3) - min(s1,s2,s3)
      value = min(value, value3)
      
print(value)

Solution (Python):

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

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    if H<W:H,W = W,H
    ans = W
    S1 = 0
    for i in range(1,H+1):
        S1 += W
        S2 = (H-i) * (W//2)
        S3 = (H-i) * (W-W//2)
        tmp = max(S1,S2,S3)-min(S1,S2,S3)
        ans = min(ans,tmp)
        
    H,W = W,H
    ans = min(ans,H)
    S1 = 0
    for i in range(1,H+1):
        S1 += W
        S2 = (H-i) * (W//2)
        S3 = (H-i) * (W-W//2)
        tmp = max(S1,S2,S3)-min(S1,S2,S3)
        ans = min(ans,tmp)
    
    
    print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()

    def solve(H,W):
        ans = inf
        for h in range(H):
            if not (H-h)&1 or not W&1:
                piece = [h*W, (W*(H-h))//2]
                ans = min(ans, max(piece)-min(piece))
            else:
                if (H-h)&1:
                    piece = [h*W, ((H-h-1)*W)//2, ((H-h+1)*W)//2]
                    ans = min(ans, max(piece)-min(piece))
                if W&1:
                    piece = [h*W, ((W-1)*(H-h))//2, ((W+1)*(H-h))//2]
                    ans = min(ans, max(piece)-min(piece))
        return ans    

    ans1 = solve(H,W)
    ans2 = solve(W,H)

    print(min(ans1,ans2))

if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    S = H*W

    def solve(H,W):
        ans = inf
        for h in range(H):
            if not (H-h)&1 or not W&1:
                piece = [h*W]
                piece.append(W*(H-h)/2)
                ans = min(ans, max(piece)-min(piece))
            else:
                if (H-h)&1:
                    piece = [h*W]
                    piece.append((H-h-1)*W/2)
                    piece.append((H-h+1)*W/2)
                    ans = min(ans, max(piece)-min(piece))
                if W&1:
                    piece = [h*W]
                    piece.append((W-1)*(H-h)/2)
                    piece.append((W+1)*(H-h)/2)
                    ans = min(ans, max(piece)-min(piece))
        return ans    

    ans1 = solve(H,W)
    ans2 = solve(W,H)

    print(int(min(ans1,ans2)))
if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    S = H*W
    ans = inf
    for h in range(H):
        if not (H-h)&1 or not W&1:
            piece = [h*W]
            piece.append(W*(H-h)/2)
            ans = min(ans, max(piece)-min(piece))
        else:
            if (H-h)&1:
                piece = [h*W]
                piece.append((H-h-1)*W/2)
                piece.append((H-h+1)*W/2)
                ans = min(ans, max(piece)-min(piece))
            if W&1:
                piece = [h*W]
                piece.append((W-1)*(H-h)/2)
                piece.append((W+1)*(H-h)/2)
                ans = min(ans, max(piece)-min(piece))
        

    for w in range(W):
        if not (W-w)&1 or not H&1:
            piece = [w*H]
            piece.append(H*(W-w)/2)
            ans = min(ans, max(piece)-min(piece))
        else:
            if (W-w)&1:
                piece = [h*W]
                piece.append((W-w-1)*H/2)
                piece.append((W-w+1)*H/2)
                ans = min(ans, max(piece)-min(piece))
            if H&1:
                piece = [h*W]
                piece.append((H-1)*(W-w)/2)
                piece.append((H+1)*(W-w)/2)
                ans = min(ans, max(piece)-min(piece))
    print(int(ans))
if __name__ == '__main__':
    main()

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

ans = H * W
for i in range(1, H):
    maxt = W * i
    tmp1 = (H - i) * (W // 2)
    tmp2 = (H - i) * (W - (W // 2))
    ans = min(ans, (max(maxt, tmp1, tmp2) - min(maxt, tmp1, tmp2)))

    tmp3 = W * ((H - i) // 2)
    tmp4 = W * (((H - i) - ((H - i) // 2)))
    ans = min(ans, (max(maxt, tmp3, tmp4) - min(maxt, tmp3, tmp4)))

for i in range(1, W):
    maxt = H * i
    tmp1 = H * ((W - i) // 2)
    tmp2 = H * ((W - i) - ((W - i) // 2))
    ans = min(ans, (max(maxt, tmp1, tmp2) - min(maxt, tmp1, tmp2)))
    tmp3 = (W - i) * (H // 2)
    tmp4 = (W - i) * (H - (H // 2))
    ans = min(ans, (max(maxt, tmp3, tmp4) - min(maxt, tmp3, tmp4)))



print(ans)

Solution (Python):
inf = float("inf")
H, W = map(int, input().split())
ans = min(W, H)
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
for i in range(1, W):
    s = [H * i, H // 2 * (W - i), (H + 1) // 2 * (W - i)]
    ans = min(ans, abs(max(s) - min(s)))
for j in range(1, H):
    s = [W * j, W // 2 * (H - j), (W + 1) // 2 * (H - j)]
    ans = min(ans, abs(max(s) - min(s)))
print(ans)

Solution (Python):
H,W=[int(i) for i in input().split()]
res = 10**15

for i in range(H):
    a = i*W
    
    h = H-i
    w = W//2
    abc = [a, h*w, h*(W-w)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    
    
    h2 = h//2
    abc = [a, h2*W, (h-h2)*W]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    

for i in range(W):
    a = H*i
    
    h = H//2
    w = W-i
    abc = [a, h*w, (H-h)*w]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    
    
    w2 = w//2
    abc = [a, H*w2, H*(w-w2)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    

print(res)