Problem:


Score : 400 points

Problem Statement

There is a bar of chocolate with a height of H blocks and a width of W blocks.
Snuke is dividing this bar into exactly three pieces.
He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.

Snuke is trying to divide the bar as evenly as possible.
More specifically, he is trying to minimize S_{max} - S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece.
Find the minimum possible value of S_{max} - S_{min}.

Constraints

2 ≤ H, W ≤ 10^5

Input

Input is given from Standard Input in the following format:

H W

Output

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

Sample Input 1

3 5

Sample Output 1

0

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

Sample Input 2

4 5

Sample Output 2

2

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

Sample Input 3

5 5

Sample Output 3

4

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

Sample Input 4

100000 2

Sample Output 4

1

Sample Input 5

100000 100000

Sample Output 5

50000



Sample input:
3 5


Sample output:
0

Submission status: Accepted

Solution code:
import sys
H,W = map(int,input().split())
if H%3 ==0:
    print(0)
    sys.exit()
if W%3 ==0:
    print(0)
    sys.exit()
A=[H,W]
for h in range(H):
    w = W//2
    sa = h*W
    sb = (H-h)*w
    sc = (H-h)*(W-w)
    A.append(max(sa,sb,sc)-min(sa,sb,sc))
for h in range(W):
    w = H//2
    sa = h*H
    sb = (W-h)*w
    sc = (W-h)*(H-w)
    A.append(max(sa,sb,sc)-min(sa,sb,sc))
print(min(A))

Submission status: Accepted

Solution code:
import sys
H,W = map(int,input().split())
if H%3 ==0:
    print(0)
    sys.exit()
if W%3 ==0:
    print(0)
    sys.exit()
A=[H,W]
for i in range(H%3+1):
    M = H//3
    if W%2==0:
        N = W//2
        A.append(abs((M+i)*W-(2*M+2-i)*N))
    else:
        N = W//2
        A.append(max((M+i)*W,(2*M+2-i)*N,(2*M+2-i)*(N+1))
                    -min((M+i)*W,(2*M+2-i)*N,(2*M+2-i)*(N+1)) )
for i in range(W%3+1):
    M = W//3
    if H%2==0:
        N = H//2
        A.append(abs((M+i)*H-(2*M+2-i)*N))
    else:
        N = H//2
        A.append(max((M+i)*H,(2*M+2-i)*N,(2*M+2-i)*(N+1))
                    -min((M+i)*H,(2*M+2-i)*N,(2*M+2-i)*(N+1)) )
print(min(A))

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
l = list(sorted([h,w]))
hh = l[0]
ww = l[1]
kouho_1 = 9999999999999999999999999999
kouho_2 = 9999999999999999999999999999
kouho_3 = 9999999999999999999999999999
kouho_4 = 9999999999999999999999999999

for i in range(1,hh):
    a = i * ww
    b = ((hh - i) // 2) * ww
    c = hh * ww - (a + b) 
    
    mi_1 = min(a,b,c)
    ma_1 = max(a,b,c)
    
    if ma_1 - mi_1 <   kouho_1 :
        kouho_1 =ma_1 - mi_1
    
    bb = ((ww // 2)) * ((hh - i))
    cc = hh * ww - a- bb
    mi_2 = min(a,bb,cc)
    ma_2 = max(a,bb,cc)
        
    if ma_2 - mi_2 < kouho_2:
        kouho_2 = ma_2 - mi_2
            
p = hh
q = ww

hh = q
ww = p

for i in range(1,hh):
    a = i * ww
    b = ((hh - i) // 2) * ww
    c = hh * ww - (a + b) 
    
    mi_1 = min(a,b,c)
    ma_1 = max(a,b,c)
    
    if ma_1 - mi_1 <   kouho_3 :
        kouho_3 =ma_1 - mi_1
    
    bb = ((ww // 2)) * ((hh - i))
    cc = hh * ww - a- bb
    mi_2 = min(a,bb,cc)
    ma_2 = max(a,bb,cc)
        
    if ma_2 - mi_2 < kouho_4:
        kouho_4 = ma_2 - mi_2
print(min(kouho_1,kouho_2,kouho_3,kouho_4))

Submission status: Accepted

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

def check(h, w):
	if h % 3 == 0 or w % 3 == 0:
		return 0

	else:
		block1 = w * (h // 3)
		block2 = (h - (h // 3)) * (w // 2)
		block3 = h * w - block1 - block2
		gap1 = max(block1, block2, block3) - min(block1, block2, block3)

		block4 = w * (h // 3 + 1)
		block5 = (h - 1 - (h // 3)) * (w // 2)
		block6 = h * w - block4 - block5
		gap2 = max(block4, block5, block6) - min(block4, block5, block6)

		return(min(gap1, gap2, min(w, h)))

print(min(check(H, W), check(W, H)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
tmp=h*w
tmp_2=h*w
tmp_3=h*w
tmp_4=h*w
for i in range(1,h):
    half_h=h-i
    area_1=i*w
    area_2=half_h//2*w
    area_3=(half_h-(half_h//2))*w
    ans=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans<tmp:
        tmp=ans
for j in range(1,w):
    half_w=w-j
    area_1=h*j
    area_2=(half_w//2)*h
    area_3=(half_w-half_w//2)*h#バグはここ
    ans_2=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_2<tmp_2:
        tmp_2=ans_2
for i in range(1,h):
    half_w=w//2
    area_1=i*half_w
    area_2=i*(w-half_w)
    area_3=(h-i)*w
    ans_3=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_3<tmp_3:
        tmp_3=ans_3
for j in range(1,w):
    half_h=h//2
    area_1=h*j
    area_2=(w-j)*half_h
    area_3=(w-j)*(h-half_h)
    ans_4=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_4<tmp_4:
        tmp_4=ans_4
print(min(tmp,tmp_2,tmp_3,tmp_4))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
    exit()
tmp=h*w
tmp_2=h*w
tmp_3=h*w
tmp_4=h*w
for i in range(1,h):
    half_h=h-i
    area_1=i*w
    area_2=half_h//2*w
    area_3=(half_h-(half_h//2))*w
    ans=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans<tmp:
        tmp=ans
for j in range(1,w):
    half_w=w-j
    area_1=h*j
    area_2=(half_w//2)*h
    area_3=(half_w-half_w//2)*h
    ans_2=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_2<tmp_2:
        tmp_2=ans_2
for i in range(1,h):
    half_w=w//2
    area_1=i*half_w
    area_2=i*(w-half_w)
    area_3=(h-i)*w
    ans_3=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_3<tmp_3:
        tmp_3=ans_3
for j in range(1,w):
    half_h=h//2
    area_1=h*j
    area_2=(w-j)*half_h
    area_3=(w-j)*(h-half_h)
    ans_4=max(area_1,area_2,area_3)-min(area_1,area_2,area_3)
    if ans_4<tmp_4:
        tmp_4=ans_4
print(min(tmp,tmp_2,tmp_3,tmp_4))

Submission status: Accepted

Solution code:
from math import ceil, floor
h, w = map(int, input().split())

def solve(H, W):
    ans = float('inf')
    for h in range(1, H):
        a = h * W
        b = (H-h) * floor(W/2)
        c = H * W - (a + b)
        d1 = max(a,b,c) - min(a,b,c)
        b = W * floor((H-h)/2)
        c = H * W - (a + b)
        d2 = max(a,b,c) - min(a,b,c)
        ans = min(d1,d2,ans)
    return ans

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

Submission status: Accepted

Solution code:
h, w = [int(x) for x in raw_input().split()]
def d(a, b):
  c = h * w - a - b
  if min(a, b, c) <= 0: return float("inf")
  return max(a, b, c) - min(a, b, c)
w2 = w // 2
w3 = w // 3
h2 = h // 2
h3 = h // 3
print min(
  d(h * w3, h * w3),
  d(h * w3, h * (w3 + 1)),
  d(h * w3, h2 * (w - w3)),
  d(h * (w3 + 1), h2 * (w - w3 - 1)),
  d(w * h3, w * h3),
  d(w * h3, w * (h3 + 1)),
  d(w * h3, w2 * (h - h3)),
  d(w * (h3 + 1), w2 * (h - h3 - 1))
)

Submission status: Accepted

Solution code:
INF = 10**10

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

res = INF
if H % 3 == 0 or W % 3 == 0:
	res = 0

def cmp1(cH, cW):
	res = INF
	for w1 in range(1, cW - 2 + 1):
		w2 = (cW - w1) // 2
		w3 = cW - w1 - w2
		s1 = cH * w1
		s2 = cH * w2
		s3 = cH * w3
		minS = min(s1, min(s2, s3))
		maxS = max(s1, max(s2, s3))
		res = min(res, maxS - minS)
	return res

def cmp2(cH, cW):
	res = INF
	w = cW // 2
	for h in range(1, cH):
		s1 = h * cW
		s2 = (cH - h) * w
		s3 = (cH - h) * (cW - w)
		minS = min(s1, min(s2, s3))
		maxS = max(s1, max(s2, s3))
		res = min(res, maxS - minS)
	return res

res = min(res, cmp1(H,W))
res = min(res, cmp1(W,H))
res = min(res, cmp2(H,W))
res = min(res, cmp2(W,H))

print(res)

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

hw = raw_input()
hw = hw.split()
hw = map(int,hw)

h = max(hw)
w = min(hw)

ans = 0

if h % 3 == 0 or w % 3 == 0:
    ans = 0
elif w % 2 == 0:
    ans = w/2
elif h % 2 == 0:
    ans = h/2
elif h == w:
    ans = (h/3+1)**2
else:
    ans = (h/3)*2+1

if ans >= w:
    ans = w

print ans

Submission status: Accepted

Solution code:
def c_bar():
	h, w = map(int, raw_input().split(" "))
	if h < 2 and w < 2:
		print "Wrong Input"
		return

	def get_min_dif(x, y):
		if x % 3 == 0 or y % 3 == 0:
			return 0
		# viewing x, get the first sub-rec
		ans = float("inf")
		for x1 in [x//3, x//3+1]:
			# view x oy y, get the other two sub-rec
			# view x
			x2 = (x - x1) // 2
			x3 = x-x1-x2
			sqrs1 = [x1*y, x2*y, x3*y]
			ans1 = max(sqrs1)-min(sqrs1)
			# view y
			y2 = y//2
			y3 = y-y2
			sqrs2 = [x1 * y, (x-x1) * y2, (x-x1) * y3]
			ans2 = max(sqrs2) - min(sqrs2)
			ans = min(ans, ans1, ans2)
		return ans
	print min(get_min_dif(h, w), get_min_dif(w, h))

if __name__ == "__main__":
	c_bar()

Submission status: Accepted

Solution code:

H, W = map(int, input().split())
# H, W = 100000, 2
# H, W = 100000, 100000

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    def solve(H, W):
        ans = float('inf')
        for h in range(1, H):
            sa = W * h
            w = W // 2
            sb = w * (H - h)
            if W - w > 0:
                sc = (W - w) * (H - h)
                ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))

            rh = (H - h) // 2
            if (H - h - rh) > 0:
                sb = W * rh
                sc = W * (H - h - rh)
                ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
        return ans
    ans = min(solve(H, W), solve(W, H))
    print(ans)

Submission status: Accepted

Solution code:
import sys

def func(H, W):
    ans = 10**9
    for w in range(1,W):
        w_a = (W - w) // 2
        w_b = W - w  - w_a
        sub = max(H * w, H * w_a, H * w_b) - min(H * w, H * w_a, H * w_b)
        ans = min(ans, sub)

        h_a = H // 2
        h_b = H - h_a
        sub = max(H * w, h_a * (W - w), h_b * (W- w)) - min(H * w, h_a * (W - w), h_b * (W- w))
        ans = min(ans , sub)
    return ans

stdin = sys.stdin

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

H, W = na()

print (min(func(H, W), func(W, H)))

Submission status: Accepted

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

def divide_h(h,w):
    mindiff = 1e12
    for x in range(1,h):
        rem_h = h - x
        s_A = x*w

        #vertical
        w1 = w//2
        s_B = w1*rem_h
        s_C = (w-w1)*rem_h

        tmp = max(s_A,s_C) - min(s_A,s_B)

        if mindiff > tmp:
            mindiff = tmp

        #horizontal
        h1 = rem_h // 2
        s_B = w * h1
        s_C = w * (rem_h - h1)
        tmp = max(s_A,s_C) - min(s_A, s_B)

        if mindiff > tmp:
            mindiff = tmp

    return mindiff

a1 = divide_h(W,H)
a2 = divide_h(H,W)

print(min(a1,a2))

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 *= 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 divide_h(h, w):
    min_diff = 1e12
    for x in range(1, h):
        h_rem = h - x
        s_A = x * w

        # vertical devide
        w1 = w // 2
        s_B = w1 * h_rem
        s_C = (w - w1) * h_rem

        tmp = max(s_A, s_B, s_C) - min(s_A, s_B, s_C)
        if min_diff > tmp:
            min_diff = tmp

        # horizontal devide
        h1 = h_rem // 2
        s_B = w * h1
        s_C = w * (h_rem - h1)
        tmp = max(s_A, s_B, s_C) - min(s_A, s_B, s_C)
        if min_diff > tmp:
            min_diff = tmp

    return min_diff



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

a1 = divide_h(H, W)
a2 = divide_h(W, H)

print(min(a1, a2))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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

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

    r = inf
    if h >= 3:
        r = w
    w1 = w//2
    w2 = (w+1)//2
    for t in range(1,h):
        a = [t*w, (h-t) * w1, (h-t) * w2]
        tr = max(a) - min(a)
        if tr < r:
            r = tr
    h1 = h//2
    h2 = (h+1)//2
    for t in range(1,w):
        a = [t*h, (w-t) * h1, (w-t) * h2]
        tr = max(a) - min(a)
        if tr < r:
            r = tr
    return r



print(main())

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:
H, W = map(int, raw_input().split())

def solve(H, W):
    S = 100000000
    for h in range(H):
        A = h * W
        B = (H - h) / 2 * W
        C = H*W - A - B
        S = min(S, max(A, B, C) - min(A, B, C))

        B = (H - h) * (W / 2)
        C = H*W - A - B
        S = min(S, max(A, B, C) - min(A, B, C))

    return S

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

Submission status: Accepted

Solution code:
import sys

inf = 1<<60
ans = inf

def solve():
    H, W = map(int, input().split())
    
    calc(H, W)
    calc(W, H)

    print(ans)

def calc(H, W):
    global ans
    x = W // 3

    s0 = x * H
    s1 = H * ((W - x + 1) // 2)
    s2 = H * ((W - x) // 2)

    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

    s1 = (W - x) * ((H + 1) // 2)
    s2 = (W - x) * (H // 2)

    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

    x = (W + 2) // 3

    s0 = x * H
    s1 = H * ((W - x + 1) // 2)
    s2 = H * ((W - x) // 2)

    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

    s1 = (W - x) * ((H + 1) // 2)
    s2 = (W - x) * (H // 2)

    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

inf = 1<<60
ans = inf

def solve():
    H, W = map(int, input().split())
    calc(H, W)
    calc(W, H)
    print(ans)

def calc(H, W):
    global ans

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

        s1 = H * ((W - a + 1) // 2)
        s2 = H * ((W - a) // 2)

        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

        s1 = (W - a) * ((H + 1) // 2)
        s2 = (W - a) * (H // 2)

        ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2)) 

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
def calculate_t(x, y):
    min_d = 1e12
    for i in range(x):
        s1 = (y//2)*i
        s2 = y*(x-i)
        s3 = (y-y//2)*i
        min_d = min(min_d, max(s1,s2,s3) - min(s1,s2,s3))
    return min_d
def calculate_3(x, y):
    min_d = 1e12
    for i in range(x):
        w1 = i
        w2 = (x-i)//2
        w3 = x - w1 -w2
        min_d = min(min_d, (max(w1,w2,w3)-min(w1,w2,w3))*y)
    return min_d
if (h*w)%3 == 0:
    print(0)
else:
    d1 = calculate_t(h,w)
    d2 = calculate_t(w,h)
    d3 = calculate_3(h,w)
    d4 = calculate_3(w,h)
    print(min(d1,d2,d3,d4))

Submission status: Accepted

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

def calc2(h, w):
    half = h // 2
    return [half * w, (h - half) * w]
    
def calc(h, w):
    a = h // 3
    slist = []
    slist.append([a * w] + calc2(h - a, w))
    slist.append([a * w] + calc2(w, h - a))
    slist.append([(a + 1) * w] + calc2(h - a - 1, w))
    slist.append([(a + 1) * w] + calc2(w, h - a - 1))
    candi = []
    for value in slist:
        candi.append(max(value) - min(value))
    return min(candi)

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

Submission status: Accepted

Solution code:
H,W=map(int,raw_input().split())
a=max([H,W]);b=min([H,W])

if H%3==0 or W%3==0:ans=0
else:
	ans=H*W
	for i in range(a/2+1):
		s1=b*i
		if (a-i)%2==0:
			s2=[(a-i)/2*b]
		else:
			s2=[(a-i)/2*b,(a-i)/2*b+b]
		if b%2==0:
			s3=[(a-i)*(b/2)]
		else:
			s3=[(a-i)*(b/2),(a-i)*(b/2)+(a-i)]

		vx=max([s1,max(s2)])
		vn=min([s1,min(s2)])
		px=max([s1,max(s3)])
		pn=min([s1,min(s3)])

		ans=min([ans,vx-vn,px-pn])

	for i in range(b/2+1):
		s1=a*i
		if (b-i)%2==0:
			s2=[(b-i)/2*a]
		else:
			s2=[(b-i)/2*a,(b-i)/2*a+a]
		if a%2==0:
			s3=[(b-i)*(a/2)]
		else:
			s3=[(b-i)*(a/2),(b-i)*(a/2)+(b-i)]

		vx=max([s1,max(s2)])
		vn=min([s1,min(s2)])
		px=max([s1,max(s3)])
		pn=min([s1,min(s3)])

		ans=min([ans,vx-vn,px-pn])

print ans

Submission status: Accepted

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1] + solve2(h, w - w2)))
        ans = min(ans, max_minus_min([area1] + solve2(w - w2, h)))
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Accepted

Solution code:
w,h=map(int,raw_input().split())
ans=10**12
for i in xrange(2):
    if i%2==1:
        w,h=h,w
    for j in xrange(1,w+1):
        a=j*h;b=(w-j)/2*h;c=(w-j+1)/2*h
        ans=min(ans,max(a,b,c)-min(a,b,c))
        b=(w-j)*(h/2);c=(w-j)*((h+1)/2)
        ans=min(ans,max(a,b,c)-min(a,b,c))
print ans

Submission status: Accepted

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h

        tmp = solve2(h, w - w2)
        tmp = max_minus_min([area1, tmp[0], tmp[1]])
        ans = min(ans, tmp)

        tmp = solve2(w - w2, h)
        tmp = max_minus_min([area1, tmp[0], tmp[1]])
        ans = min(ans, tmp)
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Accepted

Solution code:
#coding:utf-8

if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    sub = 10 ** 10

    #horizontal division
    for h in range(1, H):
        s_a = h * W

        #divide remain area vertically
        s_b = (H - h) * (W // 2)
        s_c = (H - h) * (W - (W // 2))
        sub_v = max(s_a, s_b, s_c) - min(s_a, s_b, s_c)

        #divide remain area horizontally
        s_b = ((H - h) // 2) * W
        s_c = ((H - h) - (H - h) // 2) * W
        sub_h = max(s_a, s_b, s_c) - min(s_a, s_b, s_c)

        min_sub = min(sub_v, sub_h)
        if min_sub < sub:
            sub = min_sub

    #vertical division
    for w in range(1, W):
        s_a = H * w
        #divide remain area vertically
        s_b = H * ((W - w) // 2)
        s_c = H * ((W - w) - (W - w) // 2)
        sub_v = max(s_a, s_b, s_c) - min(s_a, s_b, s_c)

        #divide remain area horizontally
        s_b = (H // 2) * (W - w)
        s_c = (H - (H // 2)) * (W - w)
        sub_h = max(s_a, s_b, s_c) - min(s_a, s_b, s_c)

        min_sub = min(sub_v, sub_h)
        if min_sub < sub:
            sub = min_sub

    print (sub)

Submission status: Accepted

Solution code:
import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b

    if fc=="ceil":
        x=math.ceil((S/3)/a)
    else:
        x=math.floor((S/3)/a)
    l=math.floor(a/2)
    S_l=(b-x)*l
    S_U=a*x
    S_r=(b-x)*(a-l)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return abs(SMax-SMin)

def solve3(a,b,dupplicate=True):
    la=math.ceil(a/3)
    lc=math.floor(a/3)
    if dupplicate:
        lb=la
    else:
        lb=lc

    Sa=la*b
    Sb=lc*b
    return abs(Sa-Sb)




s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")
s5=solve3(a,b)
s6=solve3(a,b,False)
s7=solve3(b,a)
s8=solve3(b,a,False)

print(min(s1,s2,s3,s4,s5,s6,s7,s8))

Submission status: Accepted

Solution code:
import sys
h, w = [int(i) for i in input().split()]
h3 = int(h/3)
w3 = int (w/3)
ret = sys.maxsize
# ||| Split
if(h % 3 == 0 or w % 3 == 0):
    ret = 0
a1 = h3 * w
a2 = (h3+1) * w
if(ret > a2 - a1):
    ret = a2 - a1
a1 = w3 * h
a2 = (w3+1) * h
if(ret > a2 - a1):
    ret = a2 - a1
# print("|||:", a2 - a1)
 
# T Split
a1 = h3 * w
a2 = (h-h3) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h3)
a3 = (h-h3) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin
 
# print("T1: ", amax - amin)
 
h31 = h3 + 1
a1 = (h31) * w      # 10
a2 = (h-h31) * int(w/2)  # 6
if(w % 2 == 1):
    a2 += (h-h31) # 9
a3 = (h-h31) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin
 
# print("T2: ", amax - amin, amax, amin)
 
h, w = w, h
h3 = int(h/3)
w3 = int (w/3)
a1 = h3 * w
a2 = (h-h3) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h3)
a3 = (h-h3) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin
 
# print("T3: ", amax - amin)
 
h31 = h3 + 1
a1 = (h31) * w
a2 = (h-h31) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h31)
a3 = (h-h31) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin
 
# print("T4: ", amax - amin)
 
print(int(ret))

Submission status: Accepted

Solution code:
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=10000000000
ans=INF
#超特殊例
if H%3==0 or W%3==0:
	ans=0
ans=min(ans,H,W)
#横長がある場合
for i in range(H):
	S1=W*i
	S2=int(W/2)*(H-i)
	S3=(W-int(W/2))*(H-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
for i in range(W):
	S1=H*i
	S2=int(H/2)*(W-i)
	S3=(H-int(H/2))*(W-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    H, W = ILI()
    return (H, W)

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

    if W % 2 == 0:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * W // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * (W // 2)
            num_3 = (H - h) * (W // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))

    if H % 2 == 0:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * H // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * (H // 2)
            num_3 = (W - w) * (H // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))
    
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

import math
import sys


def split_3(h, w):
    cand = []
    cand.extend([(h // 3 + i, w, h - (h // 3 + i), w) for i in range(3)])
    cand.extend([(h, w // 3 + i, h, w - (w // 3 + i)) for i in range(3)])
    return cand


def split_2(h, w):
    cand = []
    cand.extend([((h // 2 + i) * w, (h - (h // 2 + i)) * w) for i in range(2)])
    cand.extend([(h * (w // 2 + i), h * (w - (w // 2 + i))) for i in range(2)])
    return cand


def main():
    h, w = map(int, input().split())
    if h % 3 == 0 or w % 3 == 0:
        return 0

    cand = split_3(h, w)
    score = float("inf")
    for h1, w1, h2, w2 in cand:
        r1 = h1 * w1
        for r2, r3 in split_2(h2, w2):
            score = min(score, max(r1, r2, r3) - min(r1, r2, r3))
    return score


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

def calc(x,y):
  ans = float('inf')
  for x1 in [x/3, x/3+1]:
    x2 = x-x1
    xy1 = x1*y
    xy2 = x2 * (y/2 + y%2)
    xy3 = x2 * (y/2)
    ans1 = max(xy1, xy2, xy3) - min(xy1, xy2, xy3)

    xy2 = (x2/2 + x2%2) * y
    xy3 = (x2/2) * y
    ans2 = max(xy1, xy2, xy3) - min(xy1, xy2, xy3)

    ans = min(ans, ans1, ans2)
  return ans

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

Submission status: Accepted

Solution code:

def score(s, t, u):
    return max([s, t, u]) - min([s, t, u])


def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    res = w * h
    for i in range(1, h):
        s = i * w
        if (h - i) % 2 == 0 or w % 2 == 0:
            t = u = (h - i) * w // 2
            r = score(s, t, u)
            if res > r:
                res = r
        else:
            t = (h - i) // 2 * w
            u = ((h - i) // 2 + 1) * w
            r = score(s, t, u)
            if res > r:
                res = r
            t = w // 2 * (h - i)
            u = (w // 2 + 1) * (h - i)
            r = score(s, t, u)
            if res > r:
                res = r
    return res

# import sys
# sys.stdin = open('a1.in')
h, w = map(int, input().split())
res = min(solve(w, h), solve(h, w))
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,math

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

def calc(a,b,c):
    tmp = (a[0]*a[1],b[0]*b[1],c[0]*c[1])
    return max(tmp) - min(tmp)

result = H*W

#H
for i in range(H//2+1):
    a = (i,W)
    hh = H-i
    rest = (hh,W)

    result = min([result,calc(a,(hh//2,W),(hh-hh//2,W)),calc(a,(hh,W//2),(hh,W-W//2))])

#W
for i in range(W//2+1):
    a = (H,i)
    ww = W-i
    rest = (H,ww)

    result = min([result,calc(a,(H//2,ww),(H-H//2,ww)),calc(a,(H,ww//2),(H,ww-ww//2))])

print(result)

Submission status: Accepted

Solution code:
import sys

inf = 1<<60

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

    ans = inf

    # 縦(H)を固定
    for a in range(1, W):
        Ws = W - a
        s0 = H * a

        if Ws % 2 == 0 or H % 2 == 0:
            s1 = Ws * H // 2
            ans = min(ans, abs(s0 - s1))
        else:
            c = max(Ws, H)
            d = min(Ws, H)

            s1 = d * ((c + 1) // 2)
            s2 = d * (c // 2)

            ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))
            # print(s0, s1, s2)

        # print(ans)

    # 横(W)を固定
    for b in range(1, H):
        Hs = H - b
        s0 = W * b

        if Hs % 2 == 0 or W % 2 == 0:
            s1 = Hs * W // 2
            ans = min(ans, abs(s0 - s1))
        else:
            c = max(Hs, W)
            d = min(Hs, W)

            s1 = d * ((c + 1) // 2)
            s2 = d * (c // 2)

            ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

    print(ans)
    pass

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    def c(H, W):
        HW = H * W
        ans = HW
        for i in range(1, H):
            I = i * W
            O = (H - i) // 2 * W
            G = HW - I - O
            ans = min(ans, max(abs(I - O), abs(G - O), abs(G - I)))
    
        for i in range(1, H):
            I = i * W
            O = (H - i) * (W // 2)
            G = HW - I - O
            ans = min(ans, max(abs(I - O), abs(G - O), abs(G - I)))
        return ans
    
    print(min(c(H, W), c(W, H)))

main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
if H % 3 == 0 or W % 3 == 0:
	print(0)
else:
	A = []
	for j in range(2):
		if j == 1:
			H,W = W,H
		n = H // 3
		for i in range(3):
			S1 = (n + i) * W
			if W % 2 == 0:
				S2 = (H - n - i) * (W // 2)
				A.append(abs(S2 - S1))
			else:
				S2 = (H - n - i) * (W // 2)
				S3 = (H - n - i) * (W // 2 + 1)
				s = max(S1,S2,S3) - min(S1,S2,S3)
				A.append(s)
		A.append(W)
	print(min(A))

Submission status: Accepted

Solution code:
from sys import stdin
a,b = map(int,stdin.readline().split())
def get(n):
    x = []
    x.append(n/3)
    n = n-n/3
    x.append(n/2)
    x.append(n-n/2)
    return x
x = get(a)
x.sort()
y = get(b)
y.sort()
ans = []
ans.append(b*(x[-1]-x[0]))
ans.append(a*(y[-1]-y[0]))
h = a
w = b
if h > 1:
    for i in xrange(1,h):
        rem = h-i
        fir = [i*w, (h-i)*(w/2), (h-i)*(w-w/2)]
        fir.sort()
        ans.append(fir[-1]  - fir[0])
h = b
w = a
if h > 1:
    for i in xrange(1,h):
        rem = h-i
        fir = [i*w, (h-i)*(w/2), (h-i)*(w-w/2)]
        fir.sort()
        ans.append(fir[-1]  - fir[0])
ans.sort()
print ans[0]

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:
H,W = map(int, input().split())

# 4 cases

from math import floor, ceil

f = lambda x,y,z: max(x,y,z) - min(x,y,z)

def vals(H,W):
  yield (ceil(W/3)-floor(W/3))*H
  yield f(ceil(W/3)*H, (W-ceil(W/3))*floor(H/2), (W-ceil(W/3))*ceil(H/2))
  yield f(floor(W/3)*H, (W-floor(W/3))*floor(H/2), (W-floor(W/3))*ceil(H/2))


print(min(min(vals(H,W)), min(vals(W,H))))

Submission status: Accepted

Solution code:
def split_ii(h, w):
    if w==2:
        return h*w
    elif w%3==0:
        return 0
    else:
        return h

def split_t(h, w):
    ans = h*w
    for i in range(h//5, (h+1)//2+1):
        head = i*w
        left = (h-i)*(w//2)
        right = (h-i)*(w - w//2)
        ans = min(ans, max(head, left, right)-min(head, left, right))
    return ans

h, w = map(int, input().split())
print(min(split_ii(h, w), split_ii(w, h), split_t(h, w), split_t(w, h)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# import array
# from bisect import *
# from collections import *
# import fractions
# import heapq 
# from itertools import *
# import math
# import re
# import string

def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)

def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]

def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1] + solve2(h, w - w2)))
        ans = min(ans, max_minus_min([area1] + solve2(w - w2, h)))
    return ans

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