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

#+++++
		
def main():
	h, w = map(int, input().split())
	
	if h > w:
		(h,w) = (w,h)
	
	if h*w % 3 == 0:
		return 0
	
	if h==2 and w==2:
		return 1
		
	#ii
	mm=h
	
	#t
	for i in range(1, h-1 +1):
		a = w * i
		b = (w // 2) * (h - i)
		c = ((w // 2) + w % 2) * (h - i)
		rt=max(a,b,c)-min(a,b,c)
		mm=min(rt, mm)
	
	#t
	for i in range(1, w-1 +1):
		a = h * i
		b = (h // 2) * (w - i)
		c = ((h // 2) + h % 2) * (w - i)
		rt=max(a,b,c)-min(a,b,c)
		mm=min(rt, mm)	
	
	return mm
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split(' '))
    if h%3 == 0 or w%3 ==0:
        print(0)
        exit()
    ans = h*w
    for i in range(1,w):
        a=h*i
        b=(w-i)*(h//2)
        c=(w-i)*-(-h//2)
        if ans > max(a,b,c)-min(a,b,c):
            ans = max(a,b,c)-min(a,b,c)
    for j in range(1,h):
        a=w*j
        b=(h-j)*(w//2)
        c=(h-j)*-(-w//2)
        if ans > max(a,b,c)-min(a,b,c):
            ans = max(a,b,c)-min(a,b,c)
    print(min(ans,h,w))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
inf = 10 ** 9
ans1 = inf
#Hに平行な線を引く
#T字型に分割
div_h = round(h/3)
div_w = w // 2
s = [div_h * w, (h - div_h) * div_w, (h - div_h) * (w - div_w)]
ans11 = max(s) - min(s)

#三型に分割
if w < 3:
    ans12 = inf
else:
    div_h2 = (h - div_h) // 2
    s = [div_h * w, div_h2 * w, (h - div_h - div_h2) * w]
    ans12 = max(s) - min(s)
#Wに平行
div_w = round(w/3)
div_h = h // 2
s = [div_w * h, (w - div_w) * div_h, (w - div_w) * (h - div_h)]
ans21 = max(s) - min(s)

#三型に分割
if h < 3:
    ans22 = inf
else:
    div_w2 = (w - div_w) // 2
    s = [div_w * h, div_w2 * h, (w - div_w - div_w2) * h]
    ans22 = max(s) - min(s)
print(min(ans11, ans12, ans21, ans22))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



h, w = LI()
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ret = INF
    for y in range(1, h):
        ret = min(ret, max(y * w, w // 2 * (h - y), (w - w // 2) * (h - y)) - min(y * w, w // 2 * (h - y), (w - w // 2) * (h - y)))
    h, w = w, h
    for y in range(1, h):
        ret = min(ret, max(y * w, w // 2 * (h - y), (w - w // 2) * (h - y)) - min(y * w, w // 2 * (h - y), (w - w // 2) * (h - y)))
    print(min(h, w, ret))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h*w%3==0:
  print(0)
else:
  a=sorted([(h//3)*w,(h-h//3)*(w//2),(h-h//3)*(w//2+w%2)])
  b=sorted([(h//3+1)*w,(h-h//3-1)*(w//2),(h-h//3-1)*(w//2+w%2)])
  c=sorted([(w//3)*h,(w-w//3)*(h//2),(w-w//3)*(h//2+h%2)])
  d=sorted([(w//3+1)*h,(w-w//3-1)*(h//2),(w-w//3-1)*(h//2+h%2)])
  print(min(h,w,abs(a[2]-a[0]),abs(b[2]-b[0]),abs(c[2]-c[0]),abs(d[2]-d[0])))

Submission status: Accepted

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

def nasu(a, b, c):
  return max(a, b, c) - min(a, b, c)

mi = H * W
for i in range(1, H):
  x = W * i
  y = W * ((H - i) // 2)
  z = H * W - x - y
  mi = min(mi, nasu(x, y, z))
  y = (H - i) * (W // 2)
  z = H * W - x - y
  mi = min(mi, nasu(x, y, z))

for i in range(1, W):
  x = H * i
  y = H * ((W - i) // 2)
  z = H * W - x - y
  mi = min(mi, nasu(x, y, z))
  y = (W - i) * (H // 2)
  z = H * W - x - y
  mi = min(mi, nasu(x, y, z))
  
print(mi)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import ceil

def solve(H: int, W: int):
    ans = 100000000000
    if(H%3 == 0 or W%3 == 0):
        ans = 0
    
    if(H%3):
        ans = min(ans, W)
    if(W%3):
        ans = min(ans, H)
    
    for i in range(1,W):
        if(H%2):
            l = [H*i, (W-i)*(H//2), (W-i)*(H//2+1)]
            l.sort()
            # print(l)
            ans = min(ans, abs(l[2]-l[0]))
        else:
            ans = min(ans, abs(H*i-(W-i)*(H//2)))

    for i in range(1,H):
        if(W%2):
            l = [W*i, (H-i)*(W//2), (H-i)*(W//2+1)]
            l.sort()
            # print(l)
            ans = min(ans, abs(l[2]-l[0]))
        else:
            ans = min(ans, abs(W*i-(H-i)*(W//2)))

    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(H, W)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
h,w=H//2,W//3
s=sorted([w*H,(W-w)*(H-h),(W-w)*h])
a=s[2]-s[0]
s=sorted([(w+1)*H,(W-w-1)*(H-h),(W-w-1)*h])
a=min(s[2]-s[0],a)
a=min(H*(W-3*w),a)
a=min(H*(3+3*w-W),a)
h,w=H//3,W//2
s=sorted([W*h,(W-w)*(H-h),w*(H-h)])
a=min(s[2]-s[0],a)
s=sorted([W*(h+1),(W-w)*(H-h-1),w*(H-h-1)])
a=min(s[2]-s[0],a)
s=sorted([W*(h+2),(W-w)*(H-h-2),w*(H-h-2)])
a=min(s[2]-s[0],a)
a=min((H-3*h)*W,a)
a=min((3+3*h-H)*W,a)
print(a)

Submission status: Accepted

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

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

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

for i in range(1, H):
    if W % 2 == 0:
        dif = abs(i*W - (H-i)*(W//2))
    else:
        dif = max(i*W, (H-i)*((W//2)+1)) - min(i*W, (H-i)*(W//2))
    ans = min(ans, dif)

for i in range(1, W):
    if H % 2 == 0:
        dif = abs(i*H - (W-i)*(H//2))
    else:
        dif = max(i*H, (W-i)*((H//2)+1)) - min(i*H, (W-i)*(H//2))
    ans = min(ans, dif)

print(ans)

Submission status: Accepted

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

ans = float('inf')
for _ in range(2):
    for i in range(1, H):
        a = i*W

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

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,fractions
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))
def inpl_str(): return list(sys.stdin.readline().split())
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

h,w = inpl()
ans = h*w
for i in range(1,h):
    sa = i*w
    sb = math.floor((h-i)/2) * w
    sc = math.ceil((h-i)/2) * w
    dif_1 = max(sa,sb,sc) - min(sa,sb,sc)
    sb = math.floor(w/2) * (h-i)
    sc = math.ceil(w/2) * (h-i)
    dif_2 = max(sa,sb,sc) - min(sa,sb,sc)
    ans = min(ans,dif_1,dif_2)
for i in range(1,w):
    sa = i*h
    sb = math.floor((w-i)/2) * h
    sc = math.ceil((w-i)/2) * h
    dif_3 = max(sa,sb,sc) - min(sa,sb,sc)
    sb = math.floor(h/2) * (w-i)
    sc = math.ceil(h/2) * (w-i)
    dif_4 = max(sa,sb,sc) - min(sa,sb,sc)
    ans = min(ans,dif_3,dif_4)
print(ans)

Submission status: Accepted

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

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

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

    ans = int(1e10)
    for h in range(1, H):
        s1 = h * W
        tmp = (H - h) // 2
        s2 = tmp * W
        s3 = (H - h - tmp) * W
        ans = min(ans, max((s1, s2, s3)) - min((s1, s2, s3)))
        tmp = W // 2
        s2 = tmp * (H - h)
        s3 = (W - tmp) * (H - h)
        ans = min(ans, max((s1, s2, s3)) - min((s1, s2, s3)))
    for w in range(1, W):
        s1 = w * H
        tmp = (W - w) // 2
        s2 = tmp * H
        s3 = (W - w - tmp) * H
        ans = min(ans, max((s1, s2, s3)) - min((s1, s2, s3)))
        tmp = H // 2
        s2 = (W - w) * tmp
        s3 = (W - w) * (H - tmp)
        ans = min(ans, max((s1, s2, s3)) - min((s1, s2, s3)))
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=h*w
if h%3==0 or w%3==0:
  ans=0
else:
  ans=min(h,w)
a=round(h/3)*w
b=(h-round(h/3))*(w//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
a=round(w/3)*h
b=(w-round(w/3))*(h//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
print(ans)

Submission status: Accepted

Solution code:

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

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

# 3の倍数の場合、単に切って終わり
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()

def calc(ans, height, width):
    # 高さが偶数の場合、きれいにわれる
    if height % 2 == 0:
        # 1〜width-1まで全探索
        for lw in range(1, width):
            a = lw * height
            b = (width-lw) * (height//2)
            ans = min(ans, abs(a-b))
    else:
        # 高さが奇数の場合、高さ/2 の切り上げと切り下げを比較
        for lw in range(1,width):
            a = lw * height
            b = (width-lw) * (height//2)
            c = (width-lw) * (height//2 + 1)
            tmp = max(a,b,c) - min(a,b,c)
            ans = min(ans, tmp)

    return ans

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

# H/Wを入れ替え
ans = min(ans, calc(ans, W, H))

print(ans)

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]
ret = 10 ** 9 + 7

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

a, b, c = [H // 3] * 3
if H % 3 > 0:
  a += 1
if H % 3 == 2:
  b += 1

ret = min(ret, f([a, W],[b, W],[c, W]))

a, b, c = [W // 3] * 3
if W % 3 > 0:
  a += 1
if W % 3 == 2:
  b += 1

ret = min(ret, f([a, H],[b, H],[c, H]))

a, b = [W // 2] * 2
if W % 2 == 1:
  a += 1
for i in range(1, H):
  t = f([a, H - i],[b, H - i],[i, W])
  ret = min(ret, t)
  
a, b = [H // 2] * 2
if H % 2 == 1:
  a += 1
for i in range(1, W):
  t = f([a, W - i],[b, W - i],[i, H])
  ret = min(ret, t)

print(ret)

Submission status: Accepted

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

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

ans = H * W

# 縦３分割
for i in range(1, W):
    w2 = (W - i) // 2
    w3 = W - i - w2
    s1 = H * i
    s2 = H * w2
    s3 = H * w3
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)
# 横３分割
for i in range(1, H):
    h2 = (H - i) // 2
    h3 = H - i - h2
    s1 = i * W
    s2 = h2 * W
    s3 = h3 * W
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)

# 最初に縦に割る場合
for i in range(1, W):
    h2 = H // 2
    # 右側を半分にする場合
    s1 = i * H
    s2 = (W - i) * h2
    s3 = (W - i) * (H - h2)
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)
    # 左側を半分にする場合
    s1 = (W - i) * H
    s2 = i * h2
    s3 = i * (H - h2)
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)

# 最初に横に割る場合
for i in range(1, H):
    w2 = W // 2
    # 下側を半分にする場合
    s1 = W * i
    s2 = w2 * (H - i)
    s3 = (W - w2) * (H - i)
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)
    # 上側を半分にする場合
    s1 = W * (H - i)
    s2 = w2 * i
    s3 = (W - w2) * i
    diff = max(s1, s2, s3) - min(s1, s2, s3)
    ans = min(ans, diff)

print(ans)

Submission status: Accepted

Solution code:
import math

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    L = [[H,W], [W,H]]
    ans = 1e10
    for H,W in L: 
        Hp = [H, math.ceil(H/2), math.floor(H/2)]
        for x in range(1, W):
            S = [Hp[0]*x, Hp[1]*(W-x), Hp[2]*(W-x)]
            temp = max(S) - min(S)
            if ans > temp:  ans = temp

    ans = min([ans, W, H])
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

if H < W:
    H, W = W, H

S = H * W
for i in range(1, H):
    A = i * W
    BH1 = ((H-i)//2) * W
    BH2 = ((H-i)//2+(H-i)%2) * W
    BW1 = (W//2) * (H-i)
    BW2 = (W//2+W%2) * (H-i)
    SH = max(A,BH1,BH2) - min(A,BH1,BH2)
    SW = max(A,BW1,BW2) - min(A,BW1,BW2)
    S = min(S, SH, SW)

for i in range(1, W):
    A = i * H
    BH1 = ((W-i)//2) * H
    BH2 = ((W-i)//2+(W-i)%2) * H
    BW1 = (H//2) * (W-i)
    BW2 = (H//2+H%2) * (W-i)
    SH = max(A,BH1,BH2) - min(A,BH1,BH2)
    SW = max(A,BW1,BW2) - min(A,BW1,BW2)
    S = min(S, SH, SW)

print(S)

Submission status: Accepted

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

def calc(a, b):
    diff=[]
    s = [0]*3
    s[0] = a*int(b/3)
    if (a*b-s[0])%2==0:
        s[1]=int((a*b-s[0])/2)
        s[2]=s[1]
    else:
        s[1]=int(max(a,b-int(b/3))/2)*min(a,b-int(b/3))
        s[2] = a*b-s[0]-s[1]
    diff.append(max(s)-min(s))
    
    s = [0]*3
    s[0] = a*(int(b/3)+1)
    if (a*b-s[0])%2==0:
        s[1]=int((a*b-s[0])/2)
        s[2]=s[1]

    else:
        s[1]=int(max(a,(b-int(b/3)-1))/2)*min(a,(b-int(b/3)-1))
        s[2] = a*b-s[0]-s[1]
    diff.append(max(s)-min(s))
    return min(diff)

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
	print(0)
	exit()
x=[h,w]
import math
for i in range(1,w):
	p=abs(h*i-(w-i)*(h//2))
	q=abs(h*i-(w-i)*math.ceil((h/2)))
	x.append(max(p,q))
for i in range(1,h):
	p=abs(w*i-(h-i)*(w//2))
	q=abs(w*i-(h-i)*math.ceil((w/2)))
	x.append(max(p,q))
print(min(x))

Submission status: Accepted

Solution code:
# 切り方は3通りです

# 1. 縦または横に大体三等分する
# 2. 縦または横に三分の一未満で最大切り取ったあと、
#   横または縦に大体二等分する
# 3. 縦または横に三分の一以上で最大切り取ったあと、
#   横または縦に大体二等分する


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

if (H%3)*(W%3)==0:
  print(0)
else:
  d1 = min(H, W)
  ah = H//3
  h = H-ah
  d2 = abs(((W+1)//2)*h - ah*W)
  aw = W//3
  w = W-aw
  d3 = abs(((H+1)//2)*w - aw*H)
  ah = (H+2)//3
  h = H-ah
  d4 = abs((W//2)*h - ah*W)
  aw = (W+2)//3
  w = W-aw
  d5 = abs((H//2)*w - aw*H)

  print(min(d1,d2,d3,d4,d5))

Submission status: Accepted

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

Submission status: Accepted

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

ds = min(a, b)

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

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

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

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

print(ds)

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
# 2019/09/03

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

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


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

    return cnt


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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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


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

# print(ans_list)
# print(S_list)
print(min(ans_list))

Submission status: Accepted

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

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

        # 縦に割る
        w_2 = (w - w_1) // 2
        s_2 = w_2 * h

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

        ss = [s_1, s_2, s_3]
        # print(h, w, ss)
        ans = min(ans, max(ss) - min(ss))

        # 横に割る
        h_2 = h // 2
        s_2 = h_2 * (w - w_1)

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

        ss = [s_1, s_2, s_3]
        # print(h, w, ss)
        ans = min(ans, max(ss) - min(ss))

    return ans


inf = float('inf')

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(min(ans))

Submission status: Accepted

Solution code:
# ABC062C - Chocolate Bar

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

Ans = 99999999999999999
# Three Division Pattern
TDPAns = min((1 if H % 3 != 0 else 0) * W, (1 if W % 3 != 0 else 0) * H)

OTDPAns = Ans
TODPAns = Ans

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

    OTDPAns = min(OTDPAns, sub)

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

# print(f'{TDPAns}, {OTDPAns}, {TODPAns}')
print(min(TDPAns, OTDPAns, TODPAns))

Submission status: Accepted

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

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

sa = 10**100

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

tmp = h
h = w
w = tmp

yoko = h // 3

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

        
print(min(sa,h,w))

Submission status: Accepted

Solution code:
import math

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

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
stdin = sys.stdin

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

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