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 = [int(i) for i in sys.stdin.readline().split()]
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    _min = min(h,w)
    _max = max(h,w)
    s = h * w
    res = 1e9
    for x in [_max // 3, _max//3+1]:
        if (_max-x)%2==0:
            ls = [_min * x, _min*(_max - x)//2]
        elif _min % 2 == 0:
            ls = [_min * x, (s - _min * x)//2]
        else:
            __max = max(_max-x, _min)
            ls = [_min*x, (_max - x)*(__max//2), (_max-x)*(__max - __max//2)]
        res = min(res, max(ls)-min(ls))
    for y in [_min // 3, _min // 3 - 1]:
        if (_min-x)%2==0:
            ls = [_max * y, _max*(_min - y)//2]
        elif _max % 2 == 0:
            ls = [_max * y, (s - _max * y)//2]
        else:
            __max = max(_min-y, _max)
            ls = [_max*y, (_min - y)*(__max//2), (_min - y)*(__max - __max//2)]
        res = min(res, max(ls)-min(ls))
    print(res)

Submission status: Accepted

Solution code:
h, w = map(int, input().split(' '))
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    #たて
    res = h * w
    for i in range(1, w):
        A = h * i
        B_a = h * ((w - i) // 2)
        C_a = h * w - A - B_a
        B_b = (h // 2) * (w - i)
        C_b = h * w - A - B_b
        res = min(res, max(A, B_a, C_a) - min(A, B_a, C_a), max(A, B_b, C_b) - min(A, B_b, C_b))
        
    #よこ
    for i in range(1, h):
        A = w * i
        B_a = w * ((h - i) // 2)
        C_a = h * w - A - B_a
        B_b = (w // 2) * (h - i)
        C_b = h * w - A - B_b
        res = min(res, max(A, B_a, C_a) - min(A, B_a, C_a), max(A, B_b, C_b) - min(A, B_b, C_b))
        
    print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

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


ah = h//3
aw = h//3
ans = h*w
if ah:
    ans = min(ans,w)
if aw:
    ans = min(ans,h)

for i in range(1,w):
    x = h*i
    if w-i>1:
        y = ((w-i)//2)*h
        z = h*(w-i)-y
        ans =min(ans,max(x,y,z)-min(x,y,z))
    if h>1:
        y = (h//2)*(w-i)
        z = h*(w-i)-y
        ans =min(ans,max(x,y,z)-min(x,y,z))
for i in range(1,h):
    x = w*i
    if h-i>1:
        y = ((h-i)//2)*w
        z = w*(h-i)-y
        ans =min(ans,max(x,y,z)-min(x,y,z))
    if w>1:
        y = (w//2)*(h-i)
        z = w*(h-i)-y
        ans =min(ans,max(x,y,z)-min(x,y,z))

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**5
for _ in range(2):
    for i in range(1,h):
        th=(h-i)//2
        m1=max(i*w,th*w,(h-i-th)*w)-min(i*w,th*w,(h-i-th)*w)
        tw=w//2
        m2=max(i*w,(h-i)*tw,(h-i)*(w-tw))-min(i*w,(h-i)*tw,(h-i)*(w-tw))
        ans=min(ans,m1,m2)
    h,w=w,h
print(ans)

Submission status: Accepted

Solution code:
import sys

h, w = (int(i) for i in input().split())  

ans = min(h,w)

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

for i in range(1,h+1):
	ans = min(ans, max(w*i, (h-i)*(w//2), (h-i)*(w-w//2)) - min(w*i, (h-i)*(w//2), (h-i)*(w-w//2)))
for i in range(1, w+1):
	ans = min(ans, max(h*i, (w-i)*(h//2), (w-i)*(h-h//2)) - min(h*i, (w-i)*(h//2), (w-i)*(h-h//2)))

print(ans)

Submission status: Accepted

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

if H % 3 == 0:
    ans = 0
else:
    ans = W
    h_small = max(1, H // 3)
    a = W * h_small
    b = (H - h_small) * (W // 2)
    c = (H - h_small) * ((W + 1) // 2)
    ans_new = max(a, b, c) - min(a, b, c)
    ans = min(ans_new, ans)
    h_big = H // 3 + 1
    a = W * h_big
    b = (H - h_big) * (W // 2)
    c = (H - h_big) * ((W + 1) // 2)
    ans_new = max(a, b, c) - min(a, b, c)
    ans = min(ans_new, ans)
if W % 3 == 0:
    ans = 0
else:
    ans = min(H, ans)
    w_small = max(1, W // 3)
    a = H * w_small
    b = (W - w_small) * (H // 2)
    c = (W - w_small) * ((H + 1) // 2)
    ans_new = max(a, b, c) - min(a, b, c)
    ans = min(ans_new, ans)
    w_big = W // 3 + 1
    a = H * w_big
    b = (W - w_big) * (H // 2)
    c = (W - w_big) * ((H + 1) // 2)
    ans_new = max(a, b, c) - min(a, b, c)
    ans = min(ans_new, ans)

print(ans)

Submission status: Accepted

Solution code:
def threeArea(w, h, ans):
  for i in range(1, h):
    recA = w * i
    width = w//2
    recB = (h-i) * width
    recC = w * h - recA - recB
    diff = max(recA, recB, recC) - min(recA, recB, recC)
    
    height = (h - i) //2
    recB = w * height
    recC = w * h - recA - recB
    diff = min(diff, max(recA, recB, recC) - min(recA, recB, recC))
    if ans > diff:
      ans = diff
  return ans

H, W = (int(i) for i in input().split())
 
ans = float('inf')
ans = threeArea(W, H, ans)
ans = threeArea(H, W, ans)
 
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


def main():
    high, width = map(int, input().split())
    sum_s = high * width
    ans = sum_s
    for i in range(1, high):
        a = i * width
        b1 = (high - i) * (width // 2)
        b2 = ((high - i) // 2) * width
        c1 = sum_s - (a + b1)
        c2 = sum_s - (a + b2)

        ans = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2), ans)

    for i in range(1, width):
        a = i * high
        b1 = (width - i) * (high // 2)
        b2 = ((width - i) // 2) * high
        c1 = sum_s - (a + b1)
        c2 = sum_s - (a + b2)

        ans = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2), ans)

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil


def check(hs, ws):
    rtn = []
    for i in range(3):
        for j in range(i + 1, 3):
            rtn.append(abs(hs[i] * ws[i] - hs[j] * ws[j]))
    return max(rtn)


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

ans = []


hh = [ceil(h / 3), h // 3, h - ceil(h / 3) - h // 3]
ww = [w, w, w]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

h, w = w, h
hh = [ceil(h / 3), h // 3, h - ceil(h / 3) - h // 3]
ww = [w, w, w]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

hh[0] = h // 3
ww[0] = w
hh[1:3] = [h - hh[0], h - hh[0]]
ww[1:3] = [w // 2, ceil(w / 2)]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

hh[0] = ceil(h / 3)
ww[0] = w
hh[1:3] = [h - hh[0], h - hh[0]]
ww[1:3] = [w // 2, ceil(w / 2)]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

h, w = w, h
hh[0] = h // 3
ww[0] = w
hh[1:3] = [h - hh[0], h - hh[0]]
ww[1:3] = [w // 2, ceil(w / 2)]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

hh[0] = ceil(h / 3)
ww[0] = w
hh[1:3] = [h - hh[0], h - hh[0]]
ww[1:3] = [w // 2, ceil(w / 2)]
if hh.count(0) == 0 and ww.count(0) == 0:
    ans.append(check(hh, ww))

print(min(ans))

Submission status: Accepted

Solution code:
def threeArea(w, h, ans):
    for i in range(1, h):
        recA = w * i
        width = w//2
        recB = (h-i) * width
        recC = w * h - recA - recB
        diff = max(recA, recB, recC) - min(recA, recB, recC)

        height = (h - i) //2
        recB = w * height
        recC = w * h - recA - recB
        diff = min(diff, max(recA, recB, recC) - min(recA, recB, recC))
        if ans > diff:
            ans = diff
    return ans

H, W = (int(i) for i in input().split())

ans = float('inf')
ans = threeArea(W, H, ans)
ans = threeArea(H, W, ans)

print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()

if (H%3 == 0) or (W%3 == 0):
  print(0)
else:
  tate_m = H//2
  yoko_m = W//2

  ans = MAX_INT
  # 縦に切っていく
  for w in range(1,yoko_m+1):
    Area1 = H*w
    Area2 = tate_m*(W-w)
    Area3 = (H-tate_m)*(W-w)
    ans = min(ans, max(Area1,Area2,Area3)-min(Area1,Area2,Area3))

  # 横に切っていく
  for h in range(1,tate_m+1):
    Area1 = h*W
    Area2 = (H-h)*yoko_m
    Area3 = (H-h)*(W-yoko_m)
    ans = min(ans, max(Area1,Area2,Area3)-min(Area1,Area2,Area3))
  
  ans = min(ans, ((H//3)+1)*W - (H//3)*W)
  ans = min(ans, ((W//3)+1)*H - (W//3)*H)

  print(ans)

Submission status: Accepted

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

def split2(h,w):
    if h%2==0 or w%2==0:
        return h*w//2,h*w//2
    else:
        h,w = max(h,w),min(h,w)
        return h//2*w,(h+1)//2*w

ans = H*W
for i in range(1,H):
    h = H-i
    w = W
    s1 = W*i
    s2,s3 = split2(h,w)
    ans = min(max(s1,s2,s3)-min(s1,s2,s3),ans)

for i in range(1,W):
    h = H
    w = W-i
    s1 = H*i
    s2,s3 = split2(h,w)
    ans = min(max(s1,s2,s3)-min(s1,s2,s3),ans)

print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    H, W = map( int, input().split())
    ans = min(H,W)
    if H%3 == 0 or W%3 == 0:
        ans = 0
    for i in range(1,H):
        L = [W*i]
        L.append(W//2*(H-i))
        if W%2 == 1:
            L.append((W//2+1)*(H-i))
        if max(L) - min(L) < ans:
            ans = max(L) - min(L)
    for i in range(1,W):
        L = [H*i]
        L.append(H//2*(W-i))
        if H%2 == 1:
            L.append((H//2+1)*(W-i))
        if max(L) - min(L) < ans:
            ans = max(L) - min(L)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=float('inf')
for i in range(h):
    ma=max(i*w,(h-i)*(w//2),(h-i)*(-(-w//2)))
    mi=min(i*w,(h-i)*(w//2),(h-i)*(-(-w//2)))
    ma2=max(i*w,((h-i)//2)*w,(-(-(h-i)//2))*w)
    mi2=min(i*w,((h-i)//2)*w,(-(-(h-i)//2))*w)
    
    ans=min(ans, ma-mi, ma2-mi2)
    
for i in range(w):
    ma=max(i*h,(w-i)*(h//2),(w-i)*(-(-h//2)))
    mi=min(i*h,(w-i)*(h//2),(w-i)*(-(-h//2)))
    ma2=max(i*h,((w-i)//2)*h,(-(-(w-i)//2))*h)
    mi2=min(i*h,((w-i)//2)*h,(-(-(w-i)//2))*h)
    
    ans=min(ans, ma-mi, ma2-mi2)
                    
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if H%3==0 or W%3==0:
    print(0)
    exit()
def Tcheck(X,Y):
    res=X*Y
    for i in range(Y+1):
        #X*i X*(Y-i)
        Z=[X*i,(Y-i)*(X//2),(Y-i)*(X-(X//2))]
        res=min(res,max(Z)-min(Z))
    return res
print(min(H,W,Tcheck(H,W),Tcheck(W,H)))

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    hp = [H//3, H//3+1]
    ans = H*W
    for h in hp:
        S1 = h*W
        if ((H-h)*W) % 2 == 0:
            ans = min(abs((H-h)*W//2 - S1), ans)
        else:
            S2 = (H-h-1)*W//2 
            S3 = (H-h+1)*W//2
            a = max([abs(S2-S1), abs(S1-S3), abs(S3-S2)])
            S4 = (H-h)*(W+1)//2
            S5 = (H-h)*(W-1)//2
            b = max([abs(S1-S4), abs(S4-S5), abs(S5-S1)])
            ans = min([ans, a, b])
    wp = [W//3, W//3+1]
    for w in wp:
        S1 = H*w
        if ((W-w)*H) % 2 == 0:
            ans = min(abs((W-w)*H//2 - S1), ans)
        else:
            S2 = (W-w-1)*H//2 
            S3 = (W-w+1)*H//2
            a = max([abs(S2-S1), abs(S1-S3), abs(S3-S2)])
            S4 = (W-w)*(H+1)//2
            S5 = (W-w)*(H-1)//2
            b = max([abs(S1-S4), abs(S4-S5), abs(S5-S1)])
            ans = min([ans, a, b])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

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

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

    ans = min(H, W)

    for w in [W // 3, W // 3 + 1]:
        A = w * H
        for h in [H // 2, H // 2 + 1]:
            B = (W - w) * h
            C = H * W - B - A

            Smax = max(A, B, C)
            Smin = min(A, B, C)
            ans = min(ans, abs(Smax - Smin))

    for h in [H // 3, H // 3 + 1]:
        A = h * W
        for w in [W // 2, W // 2 + 1]:
            B = (H - h) * w
            C = H * W - B - A

            Smax = max(A, B, C)
            Smin = min(A, B, C)
            ans = min(ans, abs(Smax - Smin))

    print(ans)

sol()

Submission status: Accepted

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


# See:
# https://img.atcoder.jp/arc074/editorial.pdf
def calc(h, w):
    ans = float('inf')

    # Key Insight: ABCのC問題の基本は全探索
    # 分割方法は4通り
    # h, wを入れ替えれば実質2通り

    # 長方形Aの面積saを全探索
    for hi in range(1, h):
        sa = hi * w

        # 残りの長方形の扱い
        # 縦に2分割
        wi = w // 2
        sb = (h - hi) * wi
        sc = (h - hi) * (w - wi)
        ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))

        # 横に2分割
        hj = (h - hi) // 2
        sb = hj * w
        sc = (h - hi - hj) * w
        ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))

    return ans


def main():
    h, w = map(int, input().split())

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
H,W=map(int,input().split())
A=max(H,W)
B=min(H,W)
mini=10000000
if A%3==0 or B%3==0:
    print(0)
    exit(0)

for i in range(1,A):
    X=B*i
    Y=math.floor((A-i)/2)*B
    Z = math.ceil((A - i) /2) * B
    if mini>max(X,Y,Z)-min(X,Y,Z):
        mini=max(X,Y,Z)-min(X,Y,Z)

for i in range(1,A):
    X=B*i
    Y=math.floor(B/2)*(A-i)
    Z = math.ceil(B/ 2) * (A-i)
    if mini>max(X,Y,Z)-min(X,Y,Z):
        mini=max(X,Y,Z)-min(X,Y,Z)

for i in range(1,B):
    X=A*i
    Y=math.floor((B-i)/2)*A
    Z = math.ceil((B - i) / 2) * A
    if mini>max(X,Y,Z)-min(X,Y,Z):
        mini=max(X,Y,Z)-min(X,Y,Z)

for i in range(1,B):
    X=A*i
    Y=math.floor(A/2)*(A-i)
    Z = math.ceil(A/ 2) * (A-i)
    if mini>max(X,Y,Z)-min(X,Y,Z):
        mini=max(X,Y,Z)-min(X,Y,Z)

print(mini)

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 h in range(1, H+1):
    a = h*W
    #残りを高さで割る場合
    b = ((H-h)//2) * W
    c = H*W - a - b
    ans = min(ans, max([a,b,c]) - min([a,b,c]))


    #残りを幅で割る場合
    b = (H-h) * (W//2)
    c = H*W - a - b
    ans = min(ans, max([a,b,c]) - min([a,b,c]))



# 幅を変えて調べる
for w in range(1, W+1):
    a = H*w
    #残りを高さで割る場合
    b = (W-w) * (H//2)
    c = H*W - a - b
    ans = min(ans, max([a,b,c]) - min([a,b,c]))


    #残りを幅で割る場合
    b = ((W-w)//2) * H
    c = H*W - a - b
    ans = min(ans, max([a,b,c]) - min([a,b,c]))

print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    if H % 3 == 0 or W % 3 == 0: return 0
    min_d = min(H, W)
    if H % 3 != 0:
        for h in [H//3, H//3+1]:
            v1 = W*h
            v2 = (H-h)*(W//2)
            v3 = (H-h)*(W-W//2)
            min_d = min(min_d, max(v1,v2,v3)-min(v1,v2,v3))
    if W % 3 != 0:
        for w in [W//3, W//3+1]:
            v1 = H*w
            v2 = (W-w)*(H//2)
            v3 = (W-w)*(H-H//2)
            min_d = min(min_d, max(v1,v2,v3)-min(v1,v2,v3))

    return min_d

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

Submission status: Accepted

Solution code:
from math import ceil, floor
def chocolateBar():
    h,w=map(int,input().split())
    ans=10**18

    #縦に三等分する場合
    ans=min(ans, (ceil(w/3)-floor(w/3))*h )
    ans=min(ans, (ceil(h/3)-floor(h/3))*w )

    #縦横に一回ずつ
    for i in range(1, h):
        s1=i*w
        s2=(h-i)*floor(w*0.5)
        s3=(h-i)*ceil(w*0.5)
        ans=min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    for i in range(1, w):
        s1=i*h
        s2=(w-i)*floor(h*0.5)
        s3=(w-i)*ceil(h*0.5)
        ans=min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    
    return ans

print(chocolateBar())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H%3 == 0 or W%3 == 0:
  print(0)
  exit()
r = min(H, W)
def calc(a, b, c):
  a, b, c = sorted([a, b, c])
  return c-a
h = H//3
w = W//2
r = min(r, calc(h*W, (H-h)*w, (H-h)*(W-w)))
h = H//3+1
w = W//2
r = min(r, calc(h*W, (H-h)*w, (H-h)*(W-w)))
w = W//3
h = H//2
r = min(r, calc(H*w, h*(W-w), (H-h)*(W-w)))
w = W//3+1
h = H//2
r = min(r, calc(H*w, h*(W-w), (H-h)*(W-w)))
print(r)

Submission status: Accepted

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][0]) for _ in range(ps[0][1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# エントリーポイント
def main():
    H, W = input([[int], 2])

    def solve(a_max, b_max):
        min_diff = INF
        for a in range(a_max):
            # 横分割
            area1 = (a * b_max
                    , b_max // 2 * (a_max - a)
                    , (b_max // 2 + b_max % 2) * (a_max - a))
            # 縦分割
            area2 = (a * b_max
                    , (a_max - a) // 2 * b_max
                    , ((a_max - a) // 2 + (a_max - a) % 2) * b_max)
            min_diff = min(min_diff, max(area1) - min(area1), max(area2) - min(area2))
        return min_diff
    print(min(solve(H, W), solve(W, H)))

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:

import bisect
import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

h,w=getints()

def solve2(h,w):
    if h % 2 == 0:
        e = h // 2 * w
        return (e,e)
    if w % 2 == 0:
        e = h * w // 2
        return (e,e)
    h1 = h // 2
    h2 = h - h1
    e1 = (h1 * w, h2 * w)
    w1 = w // 2
    w2 = w - w1
    e2 = (h * w1, h * w2)
    return e2 if abs(e2[0] - e2[1]) < abs(e1[0] - e1[1]) else e1

def solve3():
    res = h * w
    for i in range(1, h):
        m = i * w
        r = solve2(h-i,w)
        values = list(sorted([m, r[0], r[1]]))
        res = min(res, values[2] - values[0])
    for j in range(1, w):
        m = h * j
        r = solve2(h, w - j)
        values = list(sorted([m, r[0], r[1]]))
        res = min(res, values[2] - values[0])
    return res

print(solve3())

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = 10000000000
    pieces = []
    for i in range(1, H):
        if (H - i) % 2 == 0:
            pieces = [i * W, (H - i)  // 2 * W, (H - i) // 2 * W]
        else:
            pieces = [i * W,  ((H - i) // 2 + 1) * W, ((H - i) // 2) * W]
        ans = min(ans, max(pieces) - min(pieces))
        
        if W % 2 == 0:
            pieces = [i * W, (H - i) * W // 2, (H - i) * W // 2]
        else:
            pieces = [i * W, (H - i) *  (W // 2 + 1), (H - i) * (W // 2)]
        ans = min(ans, max(pieces) - min(pieces))
        
    for i in range(1, W):
        if (W - i) % 2 == 0:
            pieces = [i * H, (W - i)  // 2 * H, (W - i) // 2 * H]
        else:
            pieces = [i * H,  ((W - i) // 2 + 1) * H, ((W - i) // 2) * H]
        ans = min(ans, max(pieces) - min(pieces))
        
        if H % 2 == 0:
            pieces = [i * H, (W - i) * H // 2, (W - i) * H // 2]
        else:
            pieces = [i * H, (W - i)  * (H // 2 + 1), (W - i) * (H // 2)]
        ans = min(ans, max(pieces) - min(pieces))
        
    print(ans)

Submission status: Accepted

Solution code:
def calc(h,w):
  ans = w
  for i in range(1,h):
    s1 = w*i
    s2 = (h-i)*(w//2)
    s3 = (h-i)*(w-w//2)
    s = [s1,s2,s3]
    ds = max(s)-min(s)
    ans = min([ans,ds])
  return ans

h,w = map(int,input().split())
if (h*w)%3==0:
  print(0)
else:
  print(min([calc(h,w),calc(w,h)]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def argmin(a):
    m, n = 1 << 31, -1
    for i, v in enumerate(a):
        if m > v:
            m, n = v, i
    return m, n


def ternary_search(f, x0, x3):
    """
    3分探索を行う。下に凸な関数fの、区間[x0, x3]内にある極値を探し、(x, f(x))を返す。
    なければ、区間の端点が返る。
    fは整数引数、x0,x3も整数引数とする。
    """
    if x0 + 2 == x3:
        xs = [x0, x0+1, x0+2]
        v, i = argmin(list(map(f, xs)))
        return xs[i], v

    x1 = (2*x0+x3)//3
    x2 = (x0+2*x3)//3

    if f(x1) >= f(x2):
        return ternary_search(f, x1, x3)
    else:
        return ternary_search(f, x0, x2)


def solve(H: int, W: int):
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return

    cand = INF
    y = 1

    def g(x, y):
        return max(x*y, W*(H-y), y*(W-x))-min(x*y, W*(H-y), y*(W-x))

    def h(x, y):
        return max(x*y, x*(H-y), H*(W-x))-min(x*y, x*(H-y), H*(W-x))

    if H == W == 2:
        print(1)
        return
    else:
        cand = min(cand, min(H, W))

    y0, y3 = 1, H-1
    x = W//2
    while y0 + 2 < y3:
        y1 = (2*y0+y3)//3
        y2 = (y0+2*y3)//3
        S1 = g(x, y1)
        S2 = g(x, y2)
        if S1 >= S2:
            y0 = y1
        else:
            y3 = y2
    ys = [y0, y0+1, y0+2]
    for y in ys:
        S = g(x, y)
        cand = min(S, cand)

    x0, x3 = 1, W-1
    y = H//2
    while x0 + 2 < x3:
        x1 = (2*x0+x3)//3
        x2 = (x0+2*x3)//3
        S1 = h(x1, y)
        S2 = h(x2, y)
        if S1 >= S2:
            x0 = x1
        else:
            x3 = x2
    xs = [x0, x0+1, x0+2]
    for x in xs:
        S = h(x, y)
        cand = min(S, cand)
    print(cand)
    return


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:
def tsep(x,y):
    m=x*y
    for i in range(1,y):
        s=[i*x,(y-i)*(x-x//2),(y-i)*(x//2)]
        m=min(m,max(s)-min(s))
    return m
H,W=map(int,input().split())
if H%3==0 or W%3==0:
    print(0)
    exit()
print(min(W,H,tsep(H,W),tsep(W,H)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    H,W = inputMap()
    
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        sys.exit()
        
    if H <= 2 and W <= 2:
        print(1)
        sys.exit()
        
    a = -(-W // 3)
    b = -(-H // 2)
    s1 = a * H
    s2 = (W-a) * b
    s3 = (W-a) * (H-b)
    ans1 = max(s1,s2,s3)-min(s1,s2,s3)
    
    a -= 1
    s1 = a * H
    s2 = (W-a) * b
    s3 = (W-a) * (H-b)
    ans2 = max(s1,s2,s3)-min(s1,s2,s3)
    
    a += 2
    s1 = a * H
    s2 = (W-a) * b
    s3 = (W-a) * (H-b)
    ans3 = max(s1,s2,s3)-min(s1,s2,s3)
    
    ans = min(ans1,ans2,ans3)
    
    tmp = W // 3
    tmp2 = (W - tmp) // 2
    s1 = tmp * H
    s2 = tmp2 * H
    s3 = (W - tmp- tmp2) * H
    ans1 = max(s1,s2,s3)-min(s1,s2,s3)
    
    tmp += 1
    s1 = tmp * H
    s2 = tmp2 * H
    s3 = (W - tmp- tmp2) * H
    ans2 = max(s1,s2,s3)-min(s1,s2,s3)
    
    tmp -= 2
    s1 = tmp * H
    s2 = tmp2 * H
    s3 = (W - tmp- tmp2) * H
    ans3 = max(s1,s2,s3)-min(s1,s2,s3)
    
    ansans = min(ans,ans1,ans2,ans3)
    
    a = -(-H // 3)
    b = -(-W // 2)
    s1 = a * W
    s2 = (H-a) * b
    s3 = (H-a) * (W-b)
    ans1 = max(s1,s2,s3)-min(s1,s2,s3)
    
    a -= 1
    s1 = a * W
    s2 = (H-a) * b
    s3 = (H-a) * (W-b)
    ans2 = max(s1,s2,s3)-min(s1,s2,s3)
    
    a += 2
    s1 = a * W
    s2 = (H-a) * b
    s3 = (H-a) * (W-b)
    ans3 = max(s1,s2,s3)-min(s1,s2,s3)
    
    ans = min(ans1,ans2,ans3)
    
    tmp = H // 3
    tmp2 = (H - tmp) // 2
    s1 = tmp * W
    s2 = tmp2 * W
    s3 = (H - tmp- tmp2) * W
    ans1 = max(s1,s2,s3)-min(s1,s2,s3)
    
    tmp += 1
    s1 = tmp * W
    s2 = tmp2 * W
    s3 = (H - tmp- tmp2) * W
    ans2 = max(s1,s2,s3)-min(s1,s2,s3)
    
    tmp -= 2
    s1 = tmp * W
    s2 = tmp2 * W
    s3 = (H - tmp- tmp2) * W
    ans3 = max(s1,s2,s3)-min(s1,s2,s3)
    
    print(min(ans,ans1,ans2,ans3,ansans))
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
ans = x*y
def compare(s1,s2,s3):
    s = [s1,s2,s3]
    s.sort()
    global ans
    ans = min(ans,abs(s[0]-s[2]))

def divide2(s1,h,w):
    compare(s1,h//2*w,(h-h//2)*w)
    compare(s1,(h//2+1)*w,(h-(h//2+1))*w)
    compare(s1,h*(w//2),h*(w-w//2))
    compare(s1,h*(w//2+1),h*(w-(w//2+1)))


def divide3(h,w):
    divide2((h//3)*w,h-h//3,w)
    divide2((h//3+1)*w,h-(h//3+1),w)
    divide2((w//3)*h,h,w-(w//3))
    divide2((w//3+1)*h,h,w-(w//3+1))

divide3(x,y)
print(ans)

Submission status: Accepted

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

def diff(a, b, c) :
    return max([a, b, c]) - min([a, b, c])

def div2(H, W, s) :
    h2, w2 = H//2, W//2
    m = float('inf')
    m = min(m, diff(s, h2*W, (H-h2)*W))
    m = min(m, diff(s, w2*H, (W-w2)*H))
    return m
    

def div3(H, W) :
    m = float('inf')
    h3, w3 = H//3, W//3
    m = min(m, div2(H-h3, W, h3*W))
    m = min(m, div2(H-(h3+1), W, (h3+1)*W))
    m = min(m, div2(H, W-w3, w3*H))
    m = min(m, div2(H, W-(w3+1), (w3+1)*H))
    return m
    
print(div3(H, W))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
can = []
hm = h//3
hp = hm+1
wm = w//3
wp = wm+1
now = [hm*w]
if (h-hm) % 2 == 0 or w % 2 == 0:
  now.append((h-hm)*w//2)
  now.append((h-hm)*w//2)
else:
  maxi = max((h-hm),w)
  mini = min((h-hm),w)
  now.append((maxi//2)*mini)
  now.append((maxi//2+1)*mini)
can.append(max(now)-min(now))
now = [hp*w]
if (h-hp) % 2 == 0 or w % 2 == 0:
  now.append((h-hp)*w//2)
  now.append((h-hp)*w//2)
else:
  maxi = max((h-hp),w)
  mini = min((h-hp),w)
  now.append((maxi//2)*mini)
  now.append((maxi//2+1)*mini)
can.append(max(now)-min(now))
now = [wm*h]
if (w-wm) % 2 == 0 or h % 2 == 0:
  now.append((w-wm)*h//2)
  now.append((w-wm)*h//2)
else:
  maxi = max((w-wm),h)
  mini = min((w-wm),h)
  now.append((maxi//2)*mini)
  now.append((maxi//2+1)*mini)
can.append(max(now)-min(now))
now = [wp*h]
if (w-wp) % 2 == 0 or h % 2 == 0:
  now.append((w-wp)*h//2)
  now.append((w-wp)*h//2)
else:
  maxi = max((w-wp),h)
  mini = min((w-wp),h)
  now.append((maxi//2)*mini)
  now.append((maxi//2+1)*mini)
can.append(max(now)-min(now))
print(min(can))

Submission status: Accepted

Solution code:
import math
H, W = map(int, input().split())
ans = 10**10
for h in range(1, H):
    A = h * W
    #残りを横に割る
    B = W*math.ceil((H-h)/2)
    C = H*W - A - B
    tmp = max([A,B,C]) - min([A,B,C])
    ans = min(ans, tmp)
    #残りを縦に割る
    B = (H-h)*math.ceil(W/2)
    C = H*W - A - B
    tmp = max([A,B,C]) - min([A,B,C])
    ans = min(ans, tmp)

# 縦横入れ替え
H, W = W, H
for h in range(1, H):
    A = h * W
    #残りを横に割る
    B = W*math.ceil((H-h)/2)
    C = H*W - A - B
    tmp = max([A,B,C]) - min([A,B,C])
    ans = min(ans, tmp)
    #残りを縦に割る
    B = (H-h)*math.ceil(W/2)
    C = H*W - A - B
    tmp = max([A,B,C]) - min([A,B,C])
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

for h in range(1,H+1):
  S1 = h*W
  S2 = (H-h)*(W//2)
  S3 = (H-h)*(W-W//2)
  Smax = max(S1,S2,S3)
  Smin = min(S1,S2,S3)
  tmp1 = Smax-Smin
  S4 = (H-h)//2*W
  S5 = ((H-h)-(H-h)//2)*W
  Smax = max(S1,S4,S5)
  Smin = min(S1,S4,S5)
  tmp2 = Smax-Smin
  ans = min(ans,tmp1,tmp2)
for w in range(1,W+1):
  S1 = H*w
  S2 = (W-w)*(H//2)
  S3 = (W-w)*(H-H//2)
  Smax = max(S1,S2,S3)
  Smin = min(S1,S2,S3)
  tmp1 = Smax-Smin
  S4 = (W-w)//2*H
  S5 = ((W-w)-(W-w)//2)*H
  Smax = max(S1,S4,S5)
  Smin = min(S1,S4,S5)
  tmp2 = Smax-Smin
  ans = min(ans,tmp1,tmp2)
print(ans)

Submission status: Accepted

Solution code:
def cut(h,w):
    d = 10 ** 9
    for i in range(1,h):
        s1 = i * w
        hh = h - i
        if hh > 1:
            j = hh // 2
            s2 = j * w
            s3 = (hh - j) * w
            smax = max(s1,s2,s3)
            smin = min(s1,s2,s3)
            if smax - smin < d:
                d = smax - smin
        
        if w >= 2:
            k = w // 2
            s2 = k * hh
            s3 = (w - k) * hh
            smax = max(s1,s2,s3)
            smin = min(s1,s2,s3)
            if smax - smin < d:
                d = smax - smin
    return d

x,y = map(int,input().split())
ans1 = cut(x,y)
ans2 = cut(y,x)
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
# ABC062C - Chocolate Bar (ARC074C)
from itertools import accumulate


def divide_bar(A: int, B: int) -> int:
    # x: one of partial rectangles
    # y: another one -> (y1, y2), (y2, y3): divide to updown, left-right
    ret = set()
    area = A * B
    for i, x in enumerate(accumulate([A] * (B // 2)), 1):
        y = area - x
        y1 = y * (A // 2) // A
        y2 = y - y1
        y3 = y * ((B - i) // 2) // (B - i)
        y4 = y - y3
        ret |= {max(x, y1, y2) - min(x, y1, y2)}
        ret |= {max(x, y3, y4) - min(x, y3, y4)}
    return min(ret)


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    ans = min(divide_bar(H, W), divide_bar(W, H))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = min(((W+2)//3 - W//3)*H, ((H+2)//3 - H//3)*W)
S = H * W
s = [0]*3

for w in range(1,W):
    s[0] = (H+1)//2*w
    s[1] = H//2*w
    s[2] = S - (s[0]+s[1])
    ans = min(ans,max(s)-min(s))

for h in range(1,H):
    s[0] = (W+1)//2*h
    s[1] = W//2*h
    s[2] = S - (s[0]+s[1])
    ans = min(ans,max(s)-min(s))

print(ans)