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:
def II(H, W):
    return 0 if W%3 == 0 else H

def T(H, W):
    if W%2 == 0:
        return W/2
    a = (H-1)/3 if H%3==1 else (H+1)/3
    b = (W+1)/2 * (H-a)
    c = (W-1)/2 * (H-a)
    a = a*W
    return max(a, b, c) - min(a, b, c)

H,W = map(int, raw_input().split())
print min(II(H, W), II(W, H), T(H, W), T(W, H))

Submission status: Accepted

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

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

def solve(h, w):
	ans = h*w

	for i in range(1, h):
		sa = i*w

		sb1 = (h-i)//2*w
		sc1 = h*w - sa - sb1

		sb2 = (h-i)*(w//2)
		sc2 = h*w - sa - sb2

		ans = min(
			ans,
			max(sa, sb1, sc1) - min(sa, sb1, sc1),
			max(sa, sb2, sc2) - min(sa, sb2, sc2)
			)

	return ans

if __name__ == '__main__':
	chocolate_bar()

Submission status: Accepted

Solution code:
import sys

h, w = [int(x) for x in sys.stdin.readline().split()]

def devider(h,w):
	if h % 3 == 0 or w % 3 == 0:
		return 0
	else:
		l1 = h // 3
		l2 = (h // 3) + 1
		d1 = something(l1,h,w)
		d2 = something(l2,h,w)
		return min(d1,d2)

def something(l,h,w):
	a = l * w
	nh = h - l
	return aaa(a, nh, w)

def aaa(a,h,w):
	d1 = dev(a, h, w)
	d2 = dev(a, w, h)
	return min(d1,d2)

def dev(a,h,w):
	lb = w // 2
	b = lb * h
	c = (w-lb) * h
	ma = max(a,b,c)
	mi = min(a,b,c)
	return ma - mi

ans = min(devider(h,w), devider(w,h))

print(ans)

Submission status: Accepted

Solution code:

# C
H, W = map(int, input().split())
 
res = min(H, W)
# split H
h = round(H / 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))
# split W
w = round(W / 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))
    
# 3
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)

Submission status: Accepted

Solution code:

# C
H, W = map(int, input().split())
 
res = min(H, W)
# split H
for h in range(H // 3, H // 3 + 2):
    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))
# split W
for w in range(W // 3, W // 3 + 2):
    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))
    
# 3
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)

Submission status: Accepted

Solution code:
# C
H, W = map(int, input().split())
 
res = min(H, W)
# split H
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))
# split W
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))
 
# 3
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)

Submission status: Accepted

Solution code:
def read(): return list(map(int, input().split()))


def calc(h, w):
    S = h * w

    ret = 1145141919
    for x in range(1, w + 1):
        s1 = h * x
        if h % 2 == 0:
            s2 = (h // 2) * (w - x)
        elif (w - x) % 2 == 0:
            s2 = ((w - x) // 2) * h
        else:
            t2 = h * ((w - x) // 2)
            t3 = S - s1 - t2

            s2 = (w - x) * (h // 2)
            s3 = S - s1 - s2

            ret = min(ret, max(s1, t2, t3) - min(s1, t2, t3), max(s1, s2, s3) - min(s1, s2, s3))
            continue

        s3 = S - s1 - s2

        smax = max(s1, s2, s3)
        smin = min(s1, s2, s3)

        ret = min(ret, smax - smin)

    return ret


def main():
    h, w = read()
    if h % 3 == 0 or w % 3 == 0:
        print(0)
        return

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def solve() :
    ri = raw_input()

    inarr = ri.split(' ')
    h = int(inarr[0])
    w = int(inarr[1])

    if h % 3 == 0 or w % 3 == 0 :
        return 0
    return min(min_diff(h,w), min_diff(w,h))

def min_diff(e1, e2) : #w,h or h,w
    score = e1
    x = e1/3
    s1 = x*e2
    s2 = (e1-x) * int(math.floor(e2/2))
    s3 = (e1 * e2) - s1 - s2
    score2 = max(abs(s1-s2), abs(s2-s3), abs(s3-s1))
    x = e1/3 + 1
    s1 = x*e2
    s2 = (e1-x) * int(math.floor(e2/2))
    s3 = (e1 * e2) - s1 - s2
    score3 = max(abs(s1-s2), abs(s2-s3), abs(s3-s1))    
    return min(score, score2, score3)

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

Submission status: Accepted

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


def main(H, W, S):  #2つに分割、Sと比較して答えを返す。
    S1 = S
    if H % 2 == 0 or W % 2 == 0:
        S2 = H * W / 2

        if S2 < S1: 
            return S1 - S2
        else:
            return S2 - S1

    else:
        S2 = max(int(H/2) * W, H * int(W/2))  
        S3 = H * W - S2
        # S2 < S3
        if S1 < S2:
            return S3 - S1
        elif S3 < S1:
            return S1 - S2
        else:
            return S3 - S2

def f(H,W):
    ans = H * W

    for S1_H in range(1, H):    #1 ~ n-1
        temp = int(main(H - S1_H, W, S1_H * W))
        if temp == 0:
            return 0
        elif temp < ans:
            ans = temp

    for S1_W in range(1, W):    #1 ~ n-1
        temp = int(main(H, W - S1_W, S1_W * H))
        if temp == 0:
            return 0
        elif temp < ans:
            ans = temp

    return ans

print(f(H,W))

Submission status: Accepted

Solution code:

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

rets = 10000000000

for i in range(1, w):
    s1 = i * h
    s2 = (w - i) * (h // 2)
    s3 = w * h - s1 - s2
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    if diff < rets:
        rets = diff

for j in range(1, h):
    s1 = j * w
    s2 = (h - j) * (w // 2)
    s3 = w * h - s1 - s2
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    if diff < rets:
        rets = diff

for k in range(1, w):
    s1 = k * h
    s2 = ((w - k) // 2) * h
    s3 = w * h - s1 - s2
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    if diff < rets:
        rets = diff

for l in range(1, h):
    s1 = l * w
    s2 = ((h - l) // 2) * w
    s3 = w * h - s1 - s2
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    if diff < rets:
        rets = diff

print(rets)

Submission status: Accepted

Solution code:

def abc_3() :
	H, W = map(int, input().split())
	print (min(div_s1(H, W), div_s1(W, H), div_s2(H, W), div_s2(W, H)))

def div_s1(H, W) :
	min_diff = 10000000000
	for w in range(1, W) :
		s1 = w * H
		s2 = ((W - w) // 2) * H
		s3 = W * H - s2 - s1
		diff = max(s1, s2, s3) - min(s1, s2, s3)
		if diff < min_diff :
			min_diff = diff
	return min_diff

def div_s2(H, W) :
	min_diff = 10000000000
	for w in range(1, W) :
		s1 = w * H
		s2 = (W - w) * (H // 2)
		s3 = W * H - s2 - s1
		diff = max(s1, s2, s3) - min(s1, s2, s3)
		if diff < min_diff :
			min_diff = diff
	return min_diff

#for i in range(5) :
#	abc_3()
#	print ('input:', end = '')
#	if input() == 'q' :
#		exit()

abc_3()

Submission status: Accepted

Solution code:

def abc_3() :
	H, W = map(int, input().split())
	print (min(div_3(H, W), div_3(W, H), div_s(H, W), div_s(W, H)))

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

def div_s(H, W) :
	min_diff = 10000000000
	for w in range(1, W) :
		s1 = w * H
		s2 = (W - w) * (H // 2)
		s3 = W * H - s2 - s1
		diff = max(s1, s2, s3) - min(s1, s2, s3)
		if diff < min_diff :
			min_diff = diff
	return min_diff

#for i in range(5) :
#	abc_3()
#	print ('input:', end = '')
#	if input() == 'q' :
#		exit()

abc_3()

Submission status: Accepted

Solution code:

def abc_3() :
	H, W = map(int, input().split())
	print (min(div_3(H, W), div_3(W, H), div_s(H, W), div_s(W, H)))

def div_3(H, W) :
	w = W //3
	if w == 0 :
		return 10000000000
	if W % 3 == 0 :
		return 0
	else :
		return H

def div_s(H, W) :
	min_diff = 10000000000
	for w in range(1, W) :
		s1 = w * H
		s2 = (W - w) * (H // 2)
		s3 = W * H - s2 - s1
		diff = max(s1, s2, s3) - min(s1, s2, s3)
		if diff < min_diff :
			min_diff = diff
	return min_diff

#for i in range(5) :
#	abc_3()
#	print ('input:', end = '')
#	if input() == 'q' :
#		break

abc_3()

Submission status: Accepted

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


def area(s):
    ans = max(s) - min(s)
    return ans


if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    temp = []
    s1 = [round(w / 3) * h, (w - round(w / 3)) * round(h / 2), round(w - w / 3) * (h - round(h / 2))]
    s2 = [round(h / 3) * w, (h - round(h / 3)) * round(w / 2), round(h - h / 3) * (w - round(w / 2))]
    temp.append(area(s1))
    temp.append(area(s2))
    if w > 2:
        s3 = [round(w / 3) * h, (w - round(w / 3) * 2) * h]
        temp.append(area(s3))
    if h > 2:
        s4 = [round(h / 3) * w, (h - round(h / 3) * 2) * w]
        temp.append(area(s4))
    ans = min(temp)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a1, a2, a3, a4 = [], [], [], []

for h in range(1, H):
	A = h * W
	B = int((H - h)//2) * W
	C = H * W - (A + B)
	D = max(A, B ,C) - min(A, B, C)
	a1.append(D)
A1 = min(a1)

for h in range(1, H):
	A = h * W
	B = int(W//2) * (H - h)
	C = H * W - (A + B)
	D = max(A, B ,C) - min(A, B, C)
	a2.append(D)
A2 = min(a2)

H, W = W, H

for h in range(1, H):
	A = h * W
	B = int((H - h)//2) * W
	C = H * W - (A + B)
	D = max(A, B ,C) - min(A, B, C)
	a3.append(D)
A3 = min(a3)

for h in range(1, H):
	A = h * W
	B = int(W//2) * (H - h)
	C = H * W - (A + B)
	D = max(A, B ,C) - min(A, B, C)
	a4.append(D)
A4 = min(a4)

print(int(min(A1, A2, A3, A4)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, raw_input().split())
 
area = [0,0,0]
ans = 10**15
if(h%3 == 0 or w%3 == 0):
    ans = 0
else:
    for i in range(1,h/2+1):
        area[0] = i*w
        tmp = w/2
        area[1] = tmp*(h-i)
        area[2] = (w-tmp)*(h-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (h-i)/2
        area[1] = tmp*w
        area[2] = (h-i-tmp)*w
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        
    for i in range(1,w/2+1):
        area[0] = i*h
        tmp = h/2
        area[1] = tmp*(w-i)
        area[2] = (h-tmp)*(w-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (w-i)/2
        area[1] = tmp*h
        area[2] = (w-i-tmp)*h
        S = max(area)-min(area)
        if(S<ans):
            ans = S
print(ans)

Submission status: Accepted

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

def div_3(H, W):
    w = W // 3
    if w == 0:
        return 10000000000
    if W % 3 == 0:
        return 0 
    else:
        return H

def w_div_h_div(H, W):
    min_diff = 10000000000
    for w in range(1, W):
        a1 = w * H
        a2 = (W - w) * (H // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(min(div_3(H, W), div_3(W, H), w_div_h_div(H, W), w_div_h_div(W, H)))

Submission status: Accepted

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

if h % 3 != 0 :
    ans = min(ans, w)
if w % 3 != 0 :
    ans = min(ans, h)

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

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

print(ans)

Submission status: Accepted

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

if (H*W)%3==0:
    print 0
else:
    s_min=float('inf')
    for _ in range(2):
        for h in range(1,H+1):
            w=W/2
            v1=(h*W,(H-h)*w,(H-h)*(W-w))
            s1=max(v1)-min(v1)
            h_p=(H-h)/2
            v2=(h*W,h_p*W,(H-h-h_p)*W)
            s2=max(v2)-min(v2)
            s=min(s1,s2)
            if s_min>s:
                s_min=s
        H,W=W,H

    print s_min

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
best = H * W
S = [0, 0, 0]
for h in range(H):
    S[0] = h * W

    S[1] = (H - h) * (W / 2)
    S[2] = (H - h) * (W - W / 2)

    if best > max(S) - min(S):
        best = max(S) - min(S)

    S[1] = (H - h) / 2 * W
    S[2] = (H - h - (H - h) / 2) * W

    if best > max(S) - min(S):
        best = max(S) - min(S)
H, W = W, H
for h in range(H):
    S[0] = h * W

    S[1] = (H - h) * (W / 2)
    S[2] = (H - h) * (W - W / 2)

    if best > max(S) - min(S):
        best = max(S) - min(S)

    S[1] = (H - h) / 2 * W
    S[2] = (H - h - (H - h) / 2) * W

    if best > max(S) - min(S):
        best = max(S) - min(S)

print best

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 == 0:
    print(0)
else:
    m = 100000000000
    for i in range(1, h):
        if m > max([i*w, (h-i)*(w//2), (h-i)*(w-(w//2))]) - min([i*w, (h-i)*(w//2), (h-i)*(w-(w//2))]):
            m = 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):
        if m > max([i*h, (w-i)*(h//2), (w-i)*(h-(h//2))]) - min([i*h, (w-i)*(h//2), (w-i)*(h-(h//2))]):
            m = max([i*h, (w-i)*(h//2), (w-i)*(h-(h//2))]) - min([i*h, (w-i)*(h//2), (w-i)*(h-(h//2))])
    if m > max([w//3, (w-(w//3))//2, w-w//3-(w-(w//3))//2])*h - min([w//3, (w-(w//3))//2, w-w//3-(w-(w//3))//2])*h:
        m = max([w//3, (w-(w//3))//2, w-w//3-(w-(w//3))//2])*h - min([w//3, (w-(w//3))//2, w-w//3-(w-(w//3))//2])*h
    if m > max([h//3, (h-(h//3))//2, h-h//3-(h-(h//3))//2])*w - min([h//3, (h-(h//3))//2, h-h//3-(h-(h//3))//2])*w:
        m = max([h//3, (h-(h//3))//2, h-h//3-(h-(h//3))//2])*w - min([h//3, (h-(h//3))//2, h-h//3-(h-(h//3))//2])*w
    print(m)

Submission status: Accepted

Solution code:
def rren(): return list(map(int, input().split()))


H, W = rren()
if(H % 3 == 0 or W % 3 == 0):
    print(0)
else:
    lis = []
    ans = 114514810
    for i in range(H):
        a = H - i
        b = i
        c = W // 2
        lis = [W*a, b*c, (W-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    for i in range(W):
        a = W - i
        b = i
        c = H // 2
        lis = [H*a, b*c, (H-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    for i in range(W//4, W//2):
        ans = min(ans, abs(i - (W-i*2))*H)
    for i in range(H//4, H//2):
        ans = min(ans, abs(i - (H-i*2))*W)
    print(ans)

Submission status: Accepted

Solution code:
n,m=list(map(int, input().split()))
lll = []
a = n
b = m
if (n * m) % 3 == 0:
    print(0)
else:
    for i in range(1, a):
        p = b * i

        if b % 2 == 1:
            q = (a - i) * (int(b / 2) + 1)
        elif b % 2 == 0:
            q = (a - i) * (int(b / 2))
        r = (a - i) * (int(b / 2))

        if (a - i) % 2 == 1:
            q2 = b * (int((a - i) / 2) + 1)
        elif (a - i) % 2 == 0:
            q2 = b * (int((a - i) / 2))

        r2 = b * (int((a - i) / 2))

        lll.append(min(max(p, q, r) - min(p, q, r), max(p, q2, r2) - min(p, q2, r2)))

    temp = b
    b = a
    a = temp
    for i in range(1, a):
        p = b * i

        if b % 2 == 1:
            q = (a - i) * (int(b / 2) + 1)
        elif b % 2 == 0:
            q = (a - i) * (int(b / 2))
        r = (a - i) * (int(b / 2))

        if (a - i) % 2 == 1:
            q2 = b * (int((a - i) / 2) + 1)
        elif (a - i) % 2 == 0:
            q2 = b * (int((a - i) / 2))

        r2 = b * (int((a - i) / 2))

        lll.append(min(max(p, q, r) - min(p, q, r), max(p, q2, r2) - min(p, q2, r2)))


    print(min(lll))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

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

def vertical_cut(H, W):
    if W < 3:
        return float('inf')

    if W % 3 == 0:
        min_w = W // 3
        max_w = W // 3
    else:
        min_w = W // 3
        max_w = W // 3 + 1

    S_max = max_w * H
    S_min = min_w * H

    return S_max - S_min

def horizontal_cut(H, W):
    return vertical_cut(W, H)

def vertical_and_horizontal_cut(H, W):
    min_score = float('inf')

    for cut_i in range(1, W // 2 + 1):
        left_S = cut_i * H
        right_W = W - cut_i

        right_H_top = H // 2
        right_H_bottom = H - right_H_top

        right_top_S = right_W * right_H_top
        right_bottom_S = right_W * right_H_bottom

        A = [left_S, right_top_S, right_bottom_S]
        score = max(A) - min(A)
        if score < min_score:
            min_score = score
    return min_score

def horizontal_and_vertical_cut(H, W):
    return vertical_and_horizontal_cut(W, H)

a = vertical_cut(H, W)
b = horizontal_cut(H, W)
c = vertical_and_horizontal_cut(H, W)
d = horizontal_and_vertical_cut(H, W)

print(min(a, b, c, d))

Submission status: Accepted

Solution code:
x, y = map(int, raw_input().split())

if x % 3 == 0 or y % 3 == 0:
	print 0
else:
	m = 10000000
	for i in range(1, x):
		j = y / 2
		s1 = y * i
		s2 = (x - i) * j
		s3 = (x - i) * (y - j)
		l = [s1, s2, s3]
		l.sort()
		if l[-1] - l[0] < m:
			m = l[-1] - l[0]
			# ix = i
			# ij = j
	# print m
	x, y = y, x
	for i in range(1, x):
		j = y / 2
		s1 = y * i
		s2 = (x - i) * j
		s3 = (x - i) * (y - j)
		l = [s1, s2, s3]
		l.sort()
		if l[-1] - l[0] < m:
			m = l[-1] - l[0]
	if m > x:
		m = x
	if m > y:
		m = y
	print m

Submission status: Accepted

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


def calc3(h, w):
        W = H = "x"
        r = []
        for a in range(h/3-3, h/3+4):
                if a < 0 or a > h:
                        continue
                for b in range(w/2-2, w/2+3):
                        if b < 0 or b > w:
                                continue
                        S1 = a * w
                        S2 = (h - a) * b
                        S3 = (h - a) * (w - b)
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
                        r.append(q)
                for b in range((h-a)/2-2, (h-a)/2+3):
                        if b < 0 or b > h-a:
                                continue
                        S1 = a * w
                        S2 = b * w
                        S3 = (h - a - b) * w
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
                        r.append(q)
        return min(r)

H, W = rdi()

print min(calc3(H, W), calc3(W, H))

Submission status: Accepted

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

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    w1 = W//3
    w2 = w1+1
    rw1 = W - w1
    rw2 = W - w2
    h1 = H//2
    h2 = H - h1
    s11 = H * w1
    s12 = rw1 * h1
    s13 = rw1 * h2
    diff1 = max(abs(s11-s12), abs(s12-s13), abs(s13-s11))
    s21 = H * w2
    s22 = rw2 * h1
    s23 = rw2 * h2
    diff2 = max(abs(s21-s22), abs(s22-s23), abs(s23-s21))
    delta1 = min(diff1, diff2)

    s31 = w1 * H
    s32 = s31
    s33 = (W - 2 * w1) * H
    delta2 = abs(s33 - s31)

    s41 = w2 * H
    s42 = s41
    s43 = (W - 2 * w2) * H
    delta3 = abs(s43 - s41)
    
    tmp = H
    H = W
    W = tmp
    
    w1 = W//3
    w2 = w1+1
    rw1 = W - w1
    rw2 = W - w2
    h1 = H//2
    h2 = H - h1
    s11 = H * w1
    s12 = rw1 * h1
    s13 = rw1 * h2
    diff1 = max(abs(s11-s12), abs(s12-s13), abs(s13-s11))
    s21 = H * w2
    s22 = rw2 * h1
    s23 = rw2 * h2
    diff2 = max(abs(s21-s22), abs(s22-s23), abs(s23-s21))
    delta4 = min(diff1, diff2)

    s31 = w1 * H
    s32 = s31
    s33 = (W - 2 * w1) * H
    delta5 = abs(s33 - s31)

    s41 = w2 * H
    s42 = s41
    s43 = (W - 2 * w2) * H
    delta6 = abs(s43 - s41)    

    print(min(delta1, delta2, delta3, delta4, delta5, delta6))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = [int(n) for n in input().split()]
S = []

if (H%3 == 0) or (W%3 == 0):
    print(0)
else:
    H_ = [(H//3), (H//3)+1, H, H]
    W_ = [W, W, W//3, (W//3) + 1]

    for h, w in zip(H_, W_):
        a = h * w
        if H != h:
            hs = H - h
        else:
            hs = H
        
        if W != w:
            ws = W - w
        else:
            ws = W

        B_ = [(hs//2)*ws, hs*(ws//2)]
        C_ = [hs*ws - b for b in B_]

        for b, c in zip(B_, C_):
            S_max = max(a, b, c)
            S_min = min(a, b, c)
            S.append(S_max - S_min)

    print(min(S))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
h,w = map(int,input().split())
if w % 3 == 0 or h % 3 == 0:
    print(0)
else:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smin = (h//3) * w
    if smax != 0:
        if w % 2 == 1:
            smax = (h - (h//3)) * (w//2 + 1)
        else:
            smax = (h - (h//3)) * (w//2)
        arr.append(smax - smin)
    #print(smax,smin)
    
    smin = (w//3) * h
    if smax != 0:
        if h % 2 == 1:
            smax = (w - (w//3)) * (h//2 + 1)
        else:
            smax = (w - (w//3)) * (h//2)
        arr.append(smax - smin)
    #print(smax,smin)
        
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))
    #print(arr)

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
	ans = 0
else:
	ans1 = min(H, W)
	if H % 2 == 0:
		ans2 = max((W // 3 + 1) * H, H // 2 * (W - W // 3 - 1)) - min((W // 3 + 1) * H, H // 2 * (W - W // 3 - 1))
		ans3 = max(W // 3 * H, H // 2 * (W - W // 3)) - min(W // 3 * H, H // 2 * (W - W // 3))
	else: 
		ans2 = max((W // 3 + 1) * H, H // 2 * (W - W // 3 - 1), (H // 2 + 1) * (W - W // 3 - 1)) - min((W // 3 + 1) * H, H // 2 * (W - W // 3 - 1), (H // 2 + 1) * (W - W // 3 - 1))
		ans3 = max(W // 3 * H, H // 2 * (W - W // 3), (H // 2 + 1) * (W - W // 3)) - min(W // 3 * H, H // 2 * (W - W // 3), (H // 2 + 1) * (W - W // 3))
	if W % 2 == 0:
		ans4 = max((H // 3 + 1) * W, W // 2 * (H - H // 3 - 1)) - min((H // 3 + 1) * W, W // 2 * (H - H // 3 - 1))
		ans5 = max(H // 3 * W, W // 2 * (H - H // 3)) - min(H // 3 * W, W // 2 * (H - H // 3))
	else:
		ans4 = max((H // 3 + 1) * W, W // 2 * (H - H // 3 - 1), (W // 2 + 1) * (H - H // 3 - 1)) - min((H // 3 + 1) * W, W // 2 * (H - H // 3 - 1), (W // 2 + 1) * (H - H // 3 - 1))
		ans5 = max(H // 3 * W, W // 2 * (H - H // 3), (W // 2 + 1) * (H - H // 3)) - min(H // 3 * W, W // 2 * (H - H // 3), (W // 2 + 1) * (H - H // 3))
	ans = min(ans1, ans2, ans3, ans4, ans5)

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
if h%3 == 0 or w%3 == 0:
  print(0)
else:
  ret = h*w
  for hi in range(max(1,h//3-10),min(h,h//3+10)):
    s1 = hi*w
    for wi in range(max(1,w//2-10),min(w,w//2+10)):
      s2 = (h-hi)*wi
      s3 = (h-hi)*(w-wi)
      d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
      ret = min(ret,d)
  for wi in range(max(1,w//3-10),min(w,w//3+10)):
    s1 = wi*h
    for hi in range(max(1,h//2-10),min(h,h//2+10)):
      s2 = (w-wi)*hi
      s3 = (w-wi)*(h-hi)
      d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
      ret = min(ret,d)
  ret = min(ret,h,w)
  print(ret)

Submission status: Accepted

Solution code:
import math

inputs = input().split(" ")
H = int(inputs[0])
W = int(inputs[1])

inf = W * 10

# case 1.
ret1 = 0 if H % 3 == 0 else  W
if H == 2:
	ret1 = inf

# case 2.
ret2 = 0 if W % 3 == 0 else H
if W == 2:
	ret2 = inf

# case 3.
ret3 = 0
idealx = W / 3
smallx = math.floor(idealx)
bigx = math.ceil(idealx)

def getDelta(h, w, x):
	if x == 0:
		return inf
	areas = [h * x, (w - x) * (h // 2), (w - x) * (h - h // 2)]
	return max(areas) - min(areas)

ret3_small = getDelta(H, W, smallx)
ret3_big = getDelta(H, W, bigx)

ret3 = min(ret3_small, ret3_big)

# case 4.
ret4 = 0
idealy = H / 3
smally = math.floor(idealy)
bigy = math.ceil(idealy)

ret4_small = getDelta(W, H, smally)
ret4_big = getDelta(W, H, bigy)

ret4 = min(ret4_small, ret4_big)

# print minof ret1-ret4s

print(min([ret1, ret2, ret3, ret4]))

Submission status: Accepted

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

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

	L = []

	l1 = []
	l1.append(H * (W // 3))
	if H % 2 == 0:
		l1.append((H / 2) * (W - (W // 3)))
	else:
		l1.append((H // 2) * (W - (W // 3)))
		l1.append((H // 2 + 1) * (W - (W // 3)))
	L.append(max(l1) - min(l1))

	l2 = []
	l2.append(H * (W // 3 + 1))
	if H % 2 == 0:
		l2.append((H / 2) * (W - (W // 3 + 1)))
	else:
		l2.append((H // 2) * (W - (W // 3 + 1)))
		l2.append((H // 2 + 1) * (W - (W // 3 + 1)))
	L.append(max(l2) - min(l2))

	l3 = []
	l3.append(W * (H // 3))
	if W % 2 == 0:
		l3.append((W / 2) * (H - (H // 3)))
	else:
		l3.append((W // 2) * (H - (H // 3)))
		l3.append((W // 2 + 1) * (H - (H // 3)))
	L.append(max(l3) - min(l3))

	l4 = []
	l4.append(W * (H // 3 + 1))
	if W % 2 == 0:
		l4.append((W / 2) * (H - (H // 3 + 1)))
	else:
		l4.append((W // 2) * (H - (H // 3 + 1)))
		l4.append((W // 2 + 1) * (H - (H // 3 + 1)))
	L.append(max(l4) - min(l4))

	mnmn = min(L)

	mn2 = min(L)

	print(int(min(mn, mn2)))

Submission status: Accepted

Solution code:
def checkW(H, W, a):
    if W % 3 == 0:
        return 0
    x = int(W / 3) + a
    y = int(H / 2)
    if x == 0 or y == 0 or (W-x) == 0:
        return 10000000000
    S = [x*H, (W-x)*y, (W-x)*(H-y)]
    #print(x, y, S, max(S),min(S))
    return max(S) - min(S)

def checkH(H, W, a):
    if H % 3 == 0:
        return 0
    x = int(W / 2)
    y = int(H / 3) + a
    if x == 0 or y == 0 or (H-y) == 0:
        return 10000000000
    S = [W*y, x*(H-y), (W-x)*(H-y)]
    #print(x, y, S, max(S),min(S))
    return max(S) - min(S)

def check(H,W):
    x = int(W/3)
    x2 = int((W-x)/2)
    x3 = int(W-x-x2)
    S = [x*H, x2*H, x3*H]
    mx = max(S) - min(S)
    y = int(H/3)
    y2 = int((H-y)/2)
    y3 = int(H-y-y2)
    S = [W*y, W*y2, W*y3]
    my = max(S) - min(S)
    return min(mx, my)

s = input().split(' ')
H = int(s[0])
W = int(s[1])
print(min(checkW(H,W,0), checkW(H,W,1),
          checkH(H,W,0), checkH(H,W,1),
          check(H,W)))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ans = 10 ** 10
    m1, m2 = m // 2, m - m // 2
    for i in range(1, n):
        S = i * m, m1 * (n - i), m2 * (n - i)
        ans = min(ans, max(S) - min(S))
    n1, n2 = n // 2, n - n // 2
    for i in range(1, m):
        S = i * n, n1 * (m - i), n2 * (m - i)
        ans = min(ans, max(S) - min(S))
    if n % 3 == 0 or m % 3 == 0: ans = 0
    if n > 2: ans = min(ans, m)
    if m > 2: ans = min(ans, n)
    assert(ans != 10 ** 10)
    print(ans)
main()

Submission status: Accepted

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

def solve(H, W):
    if H % 3 == 0 or W % 3 == 0:
        return 0
    # 横３分割または縦３分割
    record = min(H, W)

    #  ##&
    #  **&
    # (H // 2) * x
    # (H - H // 2) * x
    # (W - x) * H
    
    
    xt = (W // 3) * 2
    for x in range(max(1, xt - 100), min(W, xt + 100)):
        a1 = (H//2) * x
        a2 = H * x - a1
        a3 = (W - x) * H
        dif = max(a1, a2, a3) - min(a1, a2, a3)
        if dif < record:
            record = dif
    
    H, W = W, H
    xt = (W // 3) * 2
    for x in range(max(1, xt - 100), min(W, xt + 100)):
        a1 = (H//2) * x
        a2 = H * x - a1
        a3 = (W - x) * H
        dif = max(a1, a2, a3) - min(a1, a2, a3)
        if dif < record:
            record = dif
    
    return record

print(solve(H, W))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

sets = [
    set([1,3,5,7,8,10,12]),
    set([4,6,9,11]),
    set([2])
]

def find_group(i):
    for index, group in enumerate(sets):
        if i in group:
            return index


H,W = map(int, sys.stdin.readline().rstrip().split())

targets = []

# H -> W
for h in (H//3, H//3 + 1):
    res = H-h
    targets.append([h*W, (W//2)*res, (W-W//2)*res])
    targets.append([h*W, (res//2)*W, (res-res//2)*W])
for w in (W//3, W//3 + 1):
    res = W-w
    targets.append([w*H, (H//2)*res, (H-H//2)*res])
    targets.append([w*H, (res//2)*H, (res-res//2)*H])

print(min([
    max(target) - min(target)
    for target in targets
]))

exit(0)

Submission status: Accepted

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


def read():
    return map(int, raw_input().split())



def work((a, b)):
    def calc(h, w):
        minV = 1 << 30
        for hh in range(1, h + 1):
            area1 = hh * w
            area2 = (h - hh) / 2 * w
            area3 = (h - hh + 1) / 2 * w
            minV = min(minV, max(area1, area2, area3) - min(area1, area2, area3))
            area2 = (h - hh) * (w / 2)
            area3 = (h - hh) * ((w + 1) / 2)
            minV = min(minV, max(area1, area2, area3) - min(area1, area2, area3))
        return minV

    print min(calc(a, b), calc(b, a))


if __name__ == "__main__":
    work(read())

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
ma = max(h,w)
mi = min(h,w)
h = mi
w = ma
ans = []
if h%3==0 or w%3==0:
    print(0)
else:
    #for i in range(w//3,w//2+1):
    for i in range(1,w//2+1):
        men1 = h * i
        ma = max(h,w-i)
        mi = min(h,w-i)
        h1 = mi
        w1 = ma
        if h1%2==0 or w1%2==0:
            men2 = h1 * w1 // 2
            men3 = men2
            #print(men1,men2,men3)
            ans.append(max(men1,men2,men3)-min(men1,men2,men3))
        else:
            #print(i,w1//2,w1//2+1)
            #for j in range(w1//2,w1//2+1):
            for j in range(1,w1//2+1):
                men2 = h1 * j
                men3 = h1 * (w1 - j)
                #print(men1,men2,men3)
                ans.append(max(men1,men2,men3)-min(men1,men2,men3))
print(min(ans))