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):


import math

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

answer = 100000

for i in range(h):
    sa = i * w
    bh = math.floor((h-i)/2)
    ch = h - i - bh
    sb1 = bh * w
    sc1 = ch * w
    bw = math.floor(w/2)
    cw = w - bw
    bch = h - i
    sb2 = bw * bch
    sc2 = cw * bch
    pat1 = [sa,sb1,sc1]
    pat2 = [sa,sb2,sc2]
    pat1.sort()
    pat2.sort()
    anss = min(pat1[-1]-pat1[0],pat2[-1]-pat2[0])
    answer = min(anss,answer)

for i in range(w):
    sa = i * h
    bh = math.floor((w-i)/2)
    ch = w - i - bh
    sb1 = bh * h
    sc1 = ch * h
    bw = math.floor(h/2)
    cw = h - bw
    bch = w - i
    sb2 = bw * bch
    sc2 = cw * bch
    pat1 = [sa,sb1,sc1]
    pat2 = [sa,sb2,sc2]
    pat1.sort()
    pat2.sort()
    anss = min(pat1[-1]-pat1[0],pat2[-1]-pat2[0])
    answer = min(anss,answer)

print(answer)

Solution (Python):
def chocolate_bar(H: int, W: int)->int:
    
    h1 = H // 3
    h2 = H // 3 + (H % 3)//2
    h3 = H - h1 - h2

    min_diff = (h3 - h1) * W

    
    w1 = W // 3
    w2 = W // 3 + (W % 3)//2
    w3 = W - w1 - w2

    min_diff = min(min_diff, (w3 - w1) * H)

    
    
    
    
    
    
    h1 = round(H/3)
    h2 = H - h1
    w1 = W // 2
    w2 = W - w1

    S = [h1*W, h2*w1, h2*w2]

    min_diff = min(min_diff, max(S)-min(S))

    
    
    
    
    
    
    h1 = H // 2
    h2 = H - h1
    w1 = round(W/3)
    w2 = W - w1

    S = [H*w1, h1*w2, h2*w2]

    min_diff = min(min_diff, max(S)-min(S))

    return min_diff


if __name__ == "__main__":
    H, W = map(int, input().split())
    ans = chocolate_bar(H, W)
    print(ans)

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

def score(_list):
  return max(_list)-min(_list)

answer=H*W


for i in range(1,W//2+1):
  a=score([H*i, (W-i)*(H//2), (W-i)*(H-H//2)])
  b=score([H*i, H*((W-i)//2), H*(W-i-(W-i)//2)])
  answer=min(a,b,answer)
  

for i in range(1,H//2+1):
  a=score([W*i, (H-i)*(W//2), (H-i)*(W-W//2)])
  b=score([W*i, W*((H-i)//2), W*(H-i-(H-i)//2)])
  answer=min(a,b,answer)
  
print(answer)

Solution (Python):
H, W = map(int, input().split())
ans = (H % 3 > 0) * W
ans = min(ans, (W % 3 > 0) * H)
for h in range(1, H):
    a = h * W
    b = (H - h) * (W // 2 + (W % 2 == 1))
    c = (H - h) * (W // 2)
    ans = min(ans, max(a, b, c) - min(a, b, c))

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

Solution (Python):


import sys
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()

    if h % 3 == 0 or w % 3 == 0:
        return 0

    res = INF
    j = w // 2
    for i in range(1, h // 2 + 1):
        S = [i * w, (h - i) * j, (h - i) * (w - j)]
        res = min(res, max(S) - min(S))
        k = (h - i) // 2
        S = [i * w, k * w, ((h - i) - k) * w]
        res = min(res, max(S) - min(S))

    i = h // 2
    for j in range(1, w // 2 + 1):
        S = [j * h, (w - j) * i, (w - j) * (h - i)]
        res = min(res, max(S) - min(S))
        k = (w - j) // 2
        S = [j * h, k * h, ((w - j) - k) * h]
        res = min(res, max(S) - min(S))

    return res


print(main())

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

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

else:
    s = h * w
    l = [h,w]
    for i in range(0,2):
        if w == 2 and i == 0:
            continue
        a = (int(w/3) + i) * h
        b = (w - (int(w/3) + i)) * int(h/2)
        c = s - a - b
        
        l.append(max([a,b,c])-min([a,b,c]))
    for j in range(0,2):
        if h == 2 and j == 0:
            continue
        a = (int(h/3) + j) * w
        b = (h - (int(h/3) + j)) * int(w/2)
        c = s - a - b
        
        l.append(max([a,b,c])-min([a,b,c]))
    print(min(l))

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

for i in range(1, H+1):
    S1 = i * W
    S2_1 = (H-i) * (W//2)
    S2_2 = ((H-i)//2) * W
    S3_1 = H*W - (S1+S2_1)
    S3_2 = H*W - (S1+S2_2)
    tmp = min(max(S1, S2_1, S3_1) - min(S1, S2_1, S3_1), max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2))
    if tmp < ResMin:
        ResMin = tmp

for i in range(1, W+1):
    S1 = i * H
    S2_1 = (W-i) * (H//2)
    S2_2 = ((W-i)//2) * H
    S3_1 = H*W - (S1+S2_1)
    S3_2 = H*W - (S1+S2_2)
    tmp = min(max(S1, S2_1, S3_1) - min(S1, S2_1, S3_1), max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2))
    if tmp < ResMin:
        ResMin = tmp

print(ResMin)

Solution (Python):
H, W = map(int, input().split())
if H * W % 3 == 0:
    print(0)
else:
    ans = H * W
    Wsmall = W // 2
    for i in range(1, H + 1):
        A = i * Wsmall
        B = i * (W - Wsmall)
        C = (H - i) * W
        ans = min(ans, max(A, B, C) - min(A, B, C))
    
    Hsmall = H // 2
    for i in range(1, W + 1):
        A = Hsmall * i
        B = (H - Hsmall) * i
        C = H * (W - i)
        ans = min(ans, max(A, B, C) - min(A, B, C))

    Wsmall = W // 3
    Wbig = W // 3 + 1
    ans = min(ans, H * (Wbig - Wsmall))

    Hsmall = H // 3
    Hbig = H // 3 + 1
    ans = min(ans, (Hbig - Hsmall) * W) 
    
    print(ans)

Solution (Python):


"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""



def getIntList(): return [int(x) for x in input().split()]
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x

def prob():
    d = Debug()
    d.off()
    H, W = getIntList()
    d.dmp((H, W), 'H, W')

    
    large1 = (H+2) // 3 * W
    small1 = H // 3 * W
    large2 = (W+2) // 3 * H
    small2 = W // 3 * H
    if large1-small1 < large2-small2:
        large, small = large1, small1
    else:
        large, small = large2, small2
    d.dmp((large, small), 'large, small')
    cand = large - small

    
    area = H*W
    d.dmp((area), 'area')

    for i in range(max(1, min(H, W)//3),  (max(H, W)+1)//2+1):
        
        div1 = i*W
        div2 = (H-i)*(W//2)
        div3 = (H-i)*((W+1)//2)
        
        cand0 = max(div1, div2, div3) - min(div1, div2, div3)
        
        cand = min(cand, cand0)
        div1 = i*H
        div2 = (W-i)*(H//2)
        div3 = (W-i)*((H+1)//2)
        
        cand0 = max(div1, div2, div3) - min(div1, div2, div3)
        
        cand = min(cand, cand0)
        
    return cand


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

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

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

ans = 10**10
for h in range(1,H):
    S1 = W*h
    if W % 2 == 0:
        S2 = (W/2)*(H-h)
        S3 = (W/2)*(H-h)
    else:
        S2 = (W//2+1)*(H-h)
        S3 = (W//2)*(H-h)
    Smax = max(S1,S2)
    Smin = min(S1,S3)
    ans = min(ans , Smax - Smin )

for w in range(1,W):
    S1 = H*w
    if H % 2 == 0:
        S2 = (H/2)*(W-w)
        S3 = (H/2)*(W-w)
    else:
        S2 = (H//2+1)*(W-w)
        S3 = (H//2)*(W-w)
    Smax = max(S1,S2)
    Smin = min(S1,S3)
    ans = min(ans , Smax - Smin )

ans = min(ans , H*(W//3 +1) - H*(W//3))
ans = min(ans , W*(H//3 +1) - W*(H//3))
print(int(ans))

Solution (Python):
from math import ceil,floor

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

def S(H,W):
	res = []
	for i in range(1,H):
		S1 = i*W
		S2 = (H-i)*ceil(W/2)
		S3 = (H-i)*floor(W/2)
		S4 = W*ceil((H-i)/2)
		S5 = W*floor((H-i)/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
		res.append(max(S1,S4,S5)-min(S1,S4,S5))
	return(min(res))

print(min(S(H,W),S(W,H)))

Solution (Python):
from math import ceil,floor

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

def S(H,W):
	res = []
	for i in range(1,H):
		S1 = i*W
		S2 = (H-i)*ceil(W/2)
		S3 = (H-i)*floor(W/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
	for i in range(1,H):
		S1 = i*W
		S2 = W*ceil((H-i)/2)
		S3 = W*floor((H-i)/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
	return(min(res))

print(min(S(H,W),S(W,H)))

Solution (Python):
def solve(h, w):
    res = float('inf')
    for hh in range(h + 1):
        s1 = hh * w
        ww = w // 2
        s2 = (h - hh) * ww
        s3 = (h - hh) * (w - ww)
        res = min(res, max(s1, s2, s3) - min(s1, s2, s3))
    return res


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

ans = H * W
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    ans = min(H, W)

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

Solution (Python):
H,W=map(int,input().split())
def search(H,W):
    a=H//2
    b=H//2+H%2
    ans=float('inf')
    for w in range(1,W):
        x=a*w
        y=b*w
        z=H*(W-w)
        ans=min(ans,max(x,y,z)-min(x,y,z))
    return ans
if H%3==0 or W%3==0:
    print(0)
else:
    ans=float('inf')
    if H>3:ans=min(ans,W)
    if W>3:ans=min(ans,H)
    print(min(search(H,W),search(W,H),ans))

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

ans = float('inf')
for i in range(1,w):
    s = []
    s.append(i*h)
    if h%2 == 1:
        s.append((w-i)*(h//2+1))
    s.append((w-i)*(h//2))
    ans = min(ans,max(s)-min(s))

for i in range(1,h):
    s = []
    s.append(i*w)
    if w%2 == 1:
        s.append((h-i)*(w//2+1))
    s.append((h-i)*(w//2))
    ans = min(ans,max(s)-min(s))

ans = min(ans, h*(w//2+1) - h*(w//2), w*(h//2+1) - w*(h//2))
print(ans)

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



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


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

print( ans )

Solution (Python):
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = min(H, W)
    for h in range(1, H):
        y = (H - h) * W
        x = h * (W // 2)
        z = h * W - x
        ans = min(ans, max(x, y, z) - min(x, y, z))
    t = H
    H = W
    W = t
    for h in range(1, H):
        y = (H - h) * W
        x = h * (W // 2)
        z = h * W - x
        ans = min(ans, max(x, y, z) - min(x, y, z))
    print(ans)

Solution (Python):
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
    exit()
def main(a,b):
    ans=99999999999
    for l in range(1,a+1):
        s1=l*b
        s2=(a-l)*(b//2)
        s3=a*b-s1-s2
        s4=((a-l)//2)*b
        s5=a*b-s1-s4
        list1=sorted([s1,s2,s3])
        list2=sorted([s1,s4,s5])
        s=min((list1[-1]-list1[0]),(list2[-1]-list2[0]))
        if ans>s:
            ans=s
    return ans
print(min(main(h,w),main(w,h)))

Solution (Python):
def calcdiff(H, W, i):
    a = i * W
    b1 = (H - i) * (W//2)
    c1 = (H - i) * (W - W//2)
    ret = max(a, b1, c1) - min(a, b1, c1)
    b2 = (H - i)//2 * W
    c2 = (H - i - (H - i)//2) * W
    ret = min(ret, max(a, b2, c2) - min(a, b2, c2))
    return ret


def main():
    H, W = map(int, input().split())
    ans = float("inf")
    for i in range(1, H):
        ans = min(ans, calcdiff(H, W, i))
    for i in range(1, W):
        ans = min(ans, calcdiff(W, H, i))

    print(ans)


if __name__ == "__main__":
    main()

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

ans = [H//2+W//3+1, H//3+W//2+1, H, W]
if(H%3 == 0 or W%3 == 0):
  ans += [0]
if(H%2 == 0):
  ans += [H//2]
if(W%2 == 0):
  ans += [W//2]
print(min(ans))

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

ans = 10**10

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

ans = min(ans,w,h)

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

Solution (Python):
def main():
    h, w = map(int, input().split())
    print(min(solve(h, w), solve(w, h)))

def solve(h, w):
    m = float('inf')

    for i in range(1, h):
        a = i * w
        m = min(m, divide2(h - i, w, a))
    
    return m

def divide2(h, w, a):
    m = float('inf')
    
    if h >= 2:
        i = h // 2
        b = w * i
        c = w * (h - i)
        m = min(m, max(a, b, c) - min(a, b, c))
    
    if w >= 2:
        i = w // 2
        b = h * i
        c = h * (w - i)
        m = min(m, max(a, b, c) - min(a, b, c))
    
    return m

main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






h,w = LI()
ans = float("inf")
x = w//2
y = h//2
if not w%2:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        ans = min(ans,abs(w*i-x*(h-i)))
else:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        if w*i < x*(h-i):
            ans = min(ans,abs(w*i-(x+1)*(h-i)))
        elif w*i < (x+1)*(h-i):
            ans = min(ans,h-i)
        else:
            ans = min(ans,abs(w*i-x*(h-i)))
if not h%2:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        ans = min(ans,abs(h*i-y*(w-i)))
else:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        if h*i < y*(w-i):
            ans = min(ans,abs(h*i-(y+1)*(w-i)))
        elif h*i < (y+1)*(w-i):
            ans = min(ans,w-i)
        else:
            ans = min(ans,abs(h*i-y*(w-i)))
print(ans)

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

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

ans = min(h, w)

a = [0,0,0]
for i in range(2):
    b = h // 3 + i
    a[0] = b * w
    a[1] = (h - b) * (w // 2)
    a[2] = (h - b) * (w - (w // 2))

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

for i in range(2):
    b = w // 3 + i
    a[0] = b * h
    a[1] = (w - b) * (h // 2)
    a[2] = (w - b) * (h - (h // 2))

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

print(ans)

Solution (Python):
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:
    s=[h,w]
    for i in range(max(1,h//3-2),min(h//3+3,h-1)):
        s.append(max(w*i,((h-i)*(w//2+1)if w%2==1 else (h-i)*(w//2)))-min(w*i,(h-i)*(w//2)))
    for i in range(max(1,w//3-2),min(w//3+3,w-1)):
        s.append(max(h*i,((w-i)*(h//2+1)if h%2==1 else (w-i)*(h//2)))-min(h*i,(w-i)*(h//2)))
    print(min(s))

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

ans = float('inf')
for i in range(1, H):
    a = i * W
    b = ((H - i) // 2) * W
    c = ((H - i) - (H - i) // 2) * W
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, H):
    a = i * W
    b = (H - i) * (W // 2)
    c = (H - i) * (W - W // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, W):
    a = i * H
    b = (H // 2) * (W - i)
    c = (H - H // 2) * (W - i)
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, W):
    a = i * H
    b = ((W - i) // 2) * H
    c = ((W - i) - (W - i) // 2) * H
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)    
    
print(ans)

Solution (Python):
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    
    pattern1 = min(w, h)
    
    
    a_w = w // 2
    b_w = w - a_w
    c_w = w
    pattern2_1 = float("inf")
    for tmp_h in range(1, h + 1):
        tmp_diff = max(abs(c_w * tmp_h - a_w * (h - tmp_h)), abs(c_w * tmp_h - b_w * (h - tmp_h)))
        if tmp_diff < pattern2_1:
            pattern2_1 = tmp_diff
        else:
            break
    a_h = h // 2
    b_h = h - a_h
    c_h = h
    pattern2_2 = float("inf")
    for tmp_w in range(1, w + 1):
        tmp_diff = max(abs(c_h * tmp_w - a_h * (w - tmp_w)), abs(c_h * tmp_w - b_h * (w - tmp_w)))
        if tmp_diff < pattern2_2:
            pattern2_2 = tmp_diff
        else:
            break
    print(min(pattern1, pattern2_1, pattern2_2))

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

inf = float("inf")
ans = inf

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

case1 = [(H//3)  * W, (H-(H//3))*(W//2), (H-(H//3))*(W-W//2)]
case2 = [(H//3 + 1)  * W, (H-(H//3)-1)*(W//2), (H-(H//3)-1)*(W-W//2)]

case3 = [(W//3)  * H, (W-(W//3))*(H//2), (W-W//3) * (H-H//2)]
case4 = [(W//3 + 1)  * H, (W-(W//3)-1)*(H//2), (W-W//3 - 1) * (H-H//2)]

case5 = [H//3 * W, (H-H//3)//2 * W, (H- H//3 - (H-H//3)//2) * W] 
case6 = [W//3 * H, (W-W//3)//2 * H, (W- W//3 - (W-W//3)//2) * H] 

ans = min(ans,  max(case1) - min(case1))
ans = min(ans,  max(case2) - min(case2))
ans = min(ans,  max(case3) - min(case3))
ans = min(ans,  max(case4) - min(case4))
ans = min(ans,  max(case5) - min(case5))
ans = min(ans,  max(case6) - min(case6))

print(ans)

Solution (Python):
import math

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

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    res = 10 ** 11
    for i in range(1, H):
        a = W*i
        b = math.ceil(W/2) * (H-i)
        m = W//2 * (H-i)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, W):
        a = H*i
        b = math.ceil(H/2) * (W-i)
        m = H//2 * (W-i)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, H-1):
        a = W*i
        b = W * math.ceil((H-i)/2)
        m = W * ((H-i)//2)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, W-1):
        a = H*i
        b = H * math.ceil((W-i)/2)
        m = H * ((W-i)//2)
        res = min(res, max(a,b,m)-min(a,b,m))

               
    print(res)

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

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

Solution (Python):
H, W = map(int, input().split())
def solve(h, w):
    res = 10 ** 9
    for i in range(1, h):
        s1 = i * w
        h1 = h - i
        w1 = w // 2
        w2 = w - w //2
        s2 = h1 * w1
        s3 = h1 * w2
        diff = max([s1, s2, s3]) - min([s1, s2, s3])
        if res > diff:
            res = diff
        h2 = h1 // 2
        h3 = h1 - h1 // 2
        s2 = h2 * w
        s3 = h3 * w
        diff = max([s1, s2, s3]) - min([s1, s2, s3])
        if res > diff:
            res = diff
    return res
print(min(solve(H, W), solve(W, H)))

Solution (Python):
H, W = map(int,input().split())
ans = min(H, W)
h = round(H / 3)
w = W // 2
a = h * W
b = (H-h) * w
c = (H-h) * (W-w)
ans = min(ans, max(a, b, c) - min(a, b, c))

h = H // 2
w = round(W / 3)
a = H * w
b = (W-w) * h
c = (W-w) * (H-h)
ans = min(ans, max(a, b, c) - min(a, b, c))
if(H%3 == 0 or W%3 == 0):
  ans = 0
print(ans)

Solution (Python):
def f(h, w):
    l = []
    for i in range(w):
        m = [(w-i)*h, i*(h//2), i*(h-h//2)]
        l.append(max(m)-min(m))
    
    return min(l)

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

if 0 in [H%3, W%3]:
    print(0)
else:
    
    print(min(f(H, W), f(W, H), H, W))

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

Solution (Python):


















from collections import defaultdict, Counter
from math import pi, sqrt
from bisect import bisect_left, bisect_right

def req_S(h, w):
    tmp_s = []
    a_w = w
    for a_h in range(1, h):
        
        b_h = (h-a_h)//2
        c_h = h-b_h-a_h
        b_w, c_w = w, w
        S = [a_w*a_h, b_w*b_h, c_w*c_h]
        tmp_s.append(max(S)-min(S))
        
        b_w = w//2
        c_w = w-b_w
        b_h, c_h = h-a_h, h-a_h
        S = [a_w*a_h, b_w*b_h, c_w*c_h]
        tmp_s.append(max(S)-min(S))
    return tmp_s


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

all_S = req_S(h, w) + req_S(w, h)
print(min(all_S))

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

def calc(H,W,ans):
    for i in range(1,H):
        Sa = i * W
        h = (H-i) // 2
        Sb = h * W
        Sc = (H-i-h) * W
        d1 = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
        w = W // 2
        Sb = (H-i) * w
        Sc = (H-i) * (W-w)
        d2 = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
        if ans > min(d1,d2): ans = min(d1,d2)
    return ans

ans = 1000000
ans = calc(H,W,ans)
ans = calc(W,H,ans)

print(ans)

Solution (Python):
h, w = map(int, input().split())
ans = float("inf")
for i in range(h):
    choco = [i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(w):
    choco = [i * h, (w - i) * (h // 2), (w - i) * (h - h // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(h):
    choco = [i * w, w * ((h - i) // 2), w * ((h - i) - (h - i) // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(w):
    choco = [i * h, h * ((w - i) // 2), h * ((w - i) - (w - i) // 2)]
    ans = min(ans, max(choco) - min(choco))
print(ans)

Solution (Python):
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ans = float("inf")
    for i in range(h):
        choco = [i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(w):
        choco = [i * h, (w - i) * (h // 2), (w - i) * (h - h // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(h):
        choco = [i * w, w * ((h - i) // 2), w * ((h - i) - (h - i) // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(w):
        choco = [i * h, h * ((w - i) // 2), h * ((w - i) - (w - i) // 2)]
        ans = min(ans, max(choco) - min(choco))
    print(ans)

Solution (Python):
h,w=map(int,input().split())
ans=10**9
w1,w2=w//2,w-w//2
for i in range(1,h):
  s=i*w,w1*(h-i),w2*(h-i)
  ans=min(ans,max(s)-min(s))
h1,h2=h//2,h-h//2
for i in range(1,w):
  s=i*h,h1*(w-i),h2*(w-i)
  ans=min(ans,max(s)-min(s))
if h%3==0 or w%3==0:
  ans=0
if w >2:
  ans=min(ans,w)
if h >2:
  ans=min(ans,h)
print(ans)

Solution (Python):
def choco(h, w):

    ans = [(h % 3 != 0) * w,
           (h - (h // 3)) * (w // 2 + (w % 2 != 0)) - min( (h // 3) * w, (h - (h // 3)) * (w // 2) ),
           (h // 3  + 1) * w - (h - (h // 3 + 1)) * (w // 2)]
    return(min(ans))
    
h, w = [int(i) for i in input().split()]   
print(min(choco(h, w), choco(w, h)))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def ceil(x):
    return int((-x)//(1)*(-1))


def solve(a, b):
    """
    a,b = H,W or W,H
    aの方を三等分ぽく分解する
    """
    upper = ceil(a/3)
    lower = a//3
    l = [0]*3
    ret = float('inf')
    for i in range(lower, upper+1):
        if b % 2 == 0:
            l[0] = i*b
            l[1] = (a-i)*b//2
            l[2] = (a-i)*b//2
        else:
            l[0] = i*b
            l[1] = (a-i)*(b//2)
            l[2] = (a-i)*(b//2+1)
        ret = min(max(l)-min(l), ret, b)
    return ret


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

Solution (Python):
H ,W = map(int,input().split())
S = H*W
def ceil(i):
    if int(i) != i:
        return int(i)+1
    else:
        return int(i)

harfH1 = int(H/2)
harfH2 = ceil(H/2)
harfW1 = int(W/2)
harfW2 = ceil(W/2)
ans = 1000000000
for i in range(1,W):
    S1 = i*H
    S2 = (W-i) * harfH1 
    S3 = (W-i) * harfH2 
    diff = max(S1,S2,S3) - min(S1,S2,S3)
    ans = min(ans,diff)
for i in range(1,H):
    S1 = W*i
    S2 = harfW1 * (H-i)
    S3 = harfW2 * (H-i)
    diff = max(S1,S2,S3) - min(S1,S2,S3)
    ans = min(ans,diff)
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    ans = min(ans,W,H)
print(ans)

Solution (Python):
H,W=map(int,input().split())
minAns = float('inf')
for h in range(1,H+1):
    hh = -(-(H-h)//2)
    hd = -(-W//2)
    A = h*W
    B = hh*W
    C = (H-h-hh)*W
    D = hd*(H-h)
    E = (W-hd)*(H-h)
    M1 = max(A,B,C)
    m1 = min(A,B,C)
    M2 = max(A,D,E)
    m2 = min(A,D,E)
    minAns = min(minAns,M1-m1,M2-m2)
H,W = W,H
for h in range(1,H+1):
    hh = -(-(H-h)//2)
    hd = -(-W//2)
    A = h*W
    B = hh*W
    C = (H-h-hh)*W
    D = hd*(H-h)
    E = (W-hd)*(H-h)
    M1 = max(A,B,C)
    m1 = min(A,B,C)
    M2 = max(A,D,E)
    m2 = min(A,D,E)
    minAns = min(minAns,M1-m1,M2-m2)
print(minAns)

Solution (Python):
h,w=map(int,input().split())
pattern=[h//2+w//3+1,h//3+w//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 = []

for h in range(1,H):
    l = H-h
    cand1 = [h*W]
    cand2 = [h*W]
    cand1.append(l//2*W)
    cand1.append((l-l//2)*W)
    cand2.append(l*(W//2))
    cand2.append(l*(W-W//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))

for w in range(1,W):
    l = W-w
    cand1 = [H*w]
    cand2 = [H*w]
    cand1.append(H*(l//2))
    cand1.append(H*(l-l//2))
    cand2.append(l*(H//2))
    cand2.append(l*(H-H//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))
    
        

print(min(candidate))

Solution (Python):
def yoko3(x, w, h):
    s1 = x * w
    h2 = (h-x)//2
    s2 = h2 * w
    s3 = (h - h2 - x) * w

    s = {s1, s2, s3}

    return max(s) - min(s)


def yoko1tate2(x, w, h):
    s1 = x * w
    w2 = w // 2
    s2 = (h-x)*w2
    s3 = (h-x)*(w-w2)

    s = {s1, s2, s3}

    return max(s) - min(s)


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

    ans = float("inf")
    ans = min(ans, min([yoko3(x, W, H) for x in range(H)]))
    ans = min(ans, min([yoko3(x, H, W) for x in range(W)]))
    ans = min(ans, min([yoko1tate2(x, W, H) for x in range(H)]))
    ans = min(ans, min([yoko1tate2(x, H, W) for x in range(W)]))

    return ans


if __name__ == '__main__':
    print(solve())

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

def divide(H, W):
    if (H*W)%2 == 0:
        return H*W//2, H*W//2
    else:
        if H > W:
            return W*(H-1)//2, W*(H+1)//2
        else:
            return H*(W-1)//2, H*(W+1)//2

minval = 10000000000
for i in range(1, H):
    S0 = W*i
    S1, S2 = divide(H-i, W)
    minval = min(minval, max(abs(S0-S1), abs(S1-S2), abs(S2-S0)))
for i in range(1, W):
    S0 = H*i
    S1, S2 = divide(H, W-i)
    minval = min(minval, max(abs(S0-S1), abs(S1-S2), abs(S2-S0)))
print(minval)

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

ans1 = h * w
for i in range(1, h + 1):
    a = i * w
    b = (h - i) * (w // 2)
    c = (h - i) * (w - w // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans1 = min(ans1, tmp)
    
ans2 = h * w
for i in range(1, w + 1):
    a = i * h
    b = (w - i) * (h // 2)
    c = (w - i) * (h - h // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans2 = min(ans2, tmp)
    
ans3 = h * w
for i in range(1, h + 1):
    a = i * w
    b = (h - i) // 2 * w
    c = (h - i - (h - i) // 2) * w
    tmp = max(a, b, c) - min(a, b, c)
    ans3 = min(ans3, tmp)
    
    
ans4 = h * w
for i in range(1, h + 1):
    a = i * h
    b = (w - i) // 2 * h
    c = (w - i - (w - i) // 2) * h
    tmp = max(a, b, c) - min(a, b, c)
    ans4 = min(ans4, tmp)    
    
print(min(ans1, ans2, ans3, ans4))

Solution (Python):
H, W = map(int, input().split())
s, l = min(H, W), max(H, W)

ans = 10**6
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    for i in range(1, l):
        area1 = s*i
        area2 = s//2 * (l - i)
        area3 = area2 if s % 2 == 0 else (s//2 + 1) * (l - i)
        ans = min(ans, max(area1, area2, area3) - min(area1, area2, area3))
    for i in range(1, s):
        area1 = l*i
        area2 = l//2 * (s - i)
        area3 = area2 if l % 2 == 0 else (l//2 + 1) * (s - i)
        ans = min(ans, max(area1, area2, area3) - min(area1, area2, area3))
    ans = min(ans, H, W)
    print(ans)

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

if h * w % 3 == 0:
    ans = 0
    
else:
    ans1 = 10 ** 5
    for i in range(1, h + 1):
        a = i * w
        b = (h - i) * (w // 2)
        c = (h - i ) * (w - w // 2)
        tmp = max(a, b, c) - min(a, b, c)
        ans1 = min(ans1, tmp)
        
    ans2 = 10 ** 5
    for i in range(1, w + 1):
        a = i * h
        b = (w- i) * (h // 2)
        c = (w - i) * (h - h // 2)
        tmp = max(a, b, c) - min(a, b, c)
        ans2 = min(ans2, tmp)
        
    ans3 = 10 ** 5
    for i in range(1, h + 1):
        a = i * w
        b = (h - i) // 2 * w
        c = (h - i - (h - i) // 2) * w
        tmp = max(a, b, c) - min(a, b, c)
        ans3 = min(ans3, tmp)
        
    ans4 = 10 ** 5
    for i in range(1, w + 1):
        a = i * h
        b = (w - i) // 2 * h
        c = (w - i - (w - i) // 2) * h
        tmp = max(a, b, c) - min(a, b, c)
        ans4 = min(ans4, tmp)
        
    ans = min(ans1, ans2, ans3, ans4)
    
print(ans)