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:
h,w=map(int,input().split())
min_ = h*w
if h % 3 == 0:
  min_ = 0
else:
  min_ = min(min_, w)
if w % 3 == 0:
  min_ = 0
else:
  min_ = min(min_, h)
for i in range(1, w):
  p1 = h//2*i
  p2 = (h-h//2)*i
  p3 = h*(w-i)
  min_ = min(min_, max(p1,p2,p3)-min(p1,p2,p3))
for i in range(1, h):
  p1 = w//2*i
  p2 = (w-w//2)*i
  p3 = w*(h-i)
  min_ = min(min_, max(p1,p2,p3)-min(p1,p2,p3))
print(min_)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = h*w
for i in range(1,h):
    A = w*i
    if w%2 == 0 or (h-i)%2 == 0:
        B = ((h-i)*w)//2
        C = ((h-i)*w)//2
    else:
        if h-i <= w:
            B = (h-i)*((w//2)+1)
            C = (h-i)*(w//2)
        else:
            B = ((h-i)//2 + 1) * w
            C = ((h-i)//2) * w
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))

for i in range(1,w):
    A = h*i
    if (w-i)%2 == 0 or h%2 == 0:
        B = ((w-i)*h)//2
        C = ((w-i)*h)//2
    else:
        if w-i <= h:
            B = (w-i)*((h//2)+1)
            C = (w-i)*(h//2)
        else:
            B = ((w-i)//2 + 1) * h
            C = ((w-i)//2) * h
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))
print(ans)

Submission status: Accepted

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

ans = 10**12

# 1枚目を(1,2,...,H-1)*Wとする
for h in range(1, H):
    s1 = W * h
    # 残りは(H-h)*W

    # 残りを横に割る場合
    h2 = (H - h) // 2
    h3 = (H - h) - h2
    s2 = W * h2
    s3 = W * h3
    max_s = max(s1, s2, s3)
    min_s = min(s1, s2, s3)
    ans = min(ans, max_s - min_s)

    # 残りを縦に割る場合
    w2 = W // 2
    w3 = W - w2
    s2 = (H - h) * w2
    s3 = (H - h) * w3
    max_s = max(s1, s2, s3)
    min_s = min(s1, s2, s3)
    ans = min(ans, max_s - min_s)

# 1枚目をH*(1,2,...,W-1)とする
for w in range(1, W):
    s1 = w * H
    # 残りはH*(W-w)

    # 残りを横に割る場合
    h2 = H // 2
    h3 = H - h2
    s2 = (W - w) * h2
    s3 = (W - w) * h3
    max_s = max(s1, s2, s3)
    min_s = min(s1, s2, s3)
    ans = min(ans, max_s - min_s)

    # 残りを縦に割る場合
    w2 = (W - w) // 2
    w3 = (W - w) - w2
    s2 = H * w2
    s3 = H * w3
    max_s = max(s1, s2, s3)
    min_s = min(s1, s2, s3)
    ans = min(ans, max_s - min_s)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve(H, W):
    ans = INF
    for h in range(H + 1):
        a, b, c = h * W, (H - h) // 2 * W, (H - h + 1) // 2 * W
        ans1 = max(abs(a - b), abs(b - c), abs(c - a))
        a, b, c = h * W, (H - h) * (W // 2), (H - h) * ((W + 1) // 2)
        ans2 = max(abs(a - b), abs(b - c), abs(c - a))
        if ans > min(ans1, ans2):
            ans = min(ans1, ans2)

    return ans


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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def core(h, H, W):
    if W % 2 == 0:
        return abs(h * W - (H - h) * (W // 2))
    else:
        a, b, c = h * W, (H - h) * (W // 2), (H - h) * (W // 2 + 1)
        return max(abs(a - b), abs(b - c), abs(c - a))


def solve(H, W):
    ans = abs((H // 3) * W - ((H + 2) // 3) * W)

    if H % 3 == 0:
        ans = min(ans, core(H // 3, H, W))
    else:
        ans = min(ans, core(H // 3, H, W), core(H // 3 + 1, H, W))

    return ans


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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
h_half=h//2
w_half=w//2
s_hw=h*w
min_x=s_hw

# H*n の範囲を探査
for n in reversed(range(1,w_half+2)):
  a=h*n
  b=h_half*(w-n)
  c=s_hw-(a+b)
  s1=max(a,b,c)-min(a,b,c)
  d=(w-n)//2*h
  e=s_hw-(a+d)
  s2=max(a,d,e)-min(a,d,e)
  min_x=min(min_x,s1,s2)

# n*W の範囲を探査
for n in reversed(range(1,h_half+2)):
  a=w*n
  b=w_half*(h-n)
  c=s_hw-(a+b)
  s1=max(a,b,c)-min(a,b,c)
  d=(h-n)//2*w
  e=s_hw-(a+d)
  s2=max(a,d,e)-min(a,d,e)
  min_x=min(min_x,s1,s2)

print(min_x)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = float('inf')
for i in range(1,h):
    sa = i*w
    sb = (h-i)*int(w//2)
    sc = (h-i)*(w-int(w//2))
    sd = (h-i-int((h-i)//2))*w
    se = (int((h-i)//2))*w
    s_max1 = max(sa,sb,sc)
    s_min1 = min(sa,sb,sc)
    s_max2 = max(sa,sd,se)
    s_min2 = min(sa,sd,se)
    ans = min(ans,s_max1-s_min1,s_max2-s_min2)
for i in range(1,w):
    sa = i*h
    sb = (w-i)*int(h//2)
    sc = (w-i)*(h-int(h//2))
    sd = (w-i-int((w-i)//2))*h
    se = (int((w-i)//2))*h
    s_max1 = max(sa,sb,sc)
    s_min1 = min(sa,sb,sc)
    s_max2 = max(sa,sd,se)
    s_min2 = min(sa,sd,se)
    ans = min(ans,s_max1-s_min1,s_max2-s_min2)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a1=min(h*(w%3!=0),w*(h%3!=0))
a2=10**6
a3=10**6
for i in range(1,h):
  mx=max(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  mn=min(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  a2=min(a2,mx-mn)
for i in range(1,w):
  mx=max(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  mn=min(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  a3=min(a3,mx-mn)
print(min(a1,a2,a3))

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
from itertools import product
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def f(i, lst):
    if lst[i]:
        salaries = list(map(lambda x: f(x, lst), lst[i]))
        return max(salaries)+min(salaries)+1
    else:
        return 1

def main():
    H, W = mi()
    m = 10**100
    for h in range(H):
        S = [h*W, math.ceil((H-h)/2)*W, math.floor((H-h)/2)*W]
        m = min(max(S)-min(S), m)
    for w in range(W):
        S = [math.ceil(H/2)*w, math.floor(H/2)*w, (W-w)*H]
        m = min(max(S)-min(S), m)
    W, H = H, W
    for h in range(H):
        S = [h*W, math.ceil((H-h)/2)*W, math.floor((H-h)/2)*W]
        m = min(max(S)-min(S), m)
    for w in range(W):
        S = [math.ceil(H/2)*w, math.floor(H/2)*w, (W-w)*H]
        m = min(max(S)-min(S), m)

    print(m)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 10**10

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

for i in range(1,h):
    a = w * i
    b = (h - i) * (w // 2)
    c = (h - i) * (w - w // 2)
    ans = min(ans, max(abs(a - b), abs(b - c), abs(c - a)))

for i in range(1,w):
    a = h * i
    b = (w - i) * (h // 2)
    c = (w - i) * (h - h // 2)
    ans = min(ans, max(abs(a - b), abs(b - c), abs(c - a)))

for i in range(1,h):
    a = w * i
    b = (h - i) // 2 * w
    c = h * w - a - b
    ans = min(ans, max(abs(a - b), abs(b - c), abs(c - a)))

for i in range(1,w):
    a = h * i
    b = (w - i) // 2 * h
    c = h * w - a - b
    ans = min(ans, max(abs(a - b), abs(b - c), abs(c - a)))

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = [H//2+W//3+1,H//3+W//2+1,H,W]

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

print(min(ans))

Submission status: Accepted

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

ans = float('inf')

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

#縦割り
ans = min(ans, w)

#横割り
ans = min(ans, h)

#縦割り+横半分
for x in range(1, w+1):
    tate_area = x*h
    yoko_min_area = (w-x)*(h//2)
    yoko_max_area = (w-x)*(h-h//2)
    area_max = max(tate_area, yoko_min_area, yoko_max_area)
    area_min = min(tate_area, yoko_min_area, yoko_max_area)
    ans = min(ans, area_max-area_min)
    #print(ans, tate_area, yoko_min_area, yoko_max_area)

#横割り+縦半分
for y in range(h//3, h+1):
    yoko_area = y*w
    tate_min_area = (h-y)*(w//2)
    tate_max_area = (h-y)*(w-w//2)
    area_max = max(yoko_area, tate_min_area, tate_max_area)
    area_min = min(yoko_area, tate_min_area, tate_max_area)
    ans = min(ans, area_max-area_min)

print(ans)

Submission status: Accepted

Solution code:
def answer(H,W,ans):
    global ans_list
    for x in range(1,W):
        y1 = H // 2
        S1 = [H * x,(W - x) * y1,(W - x) * (H - y1)]
        ans_list.append(max(S1)-min(S1))

        y2 = (W - x) // 2
        S2 = [H * x,H * y2,H * (W - x - y2)]
        ans_list.append(max(S2)-min(S2))

if __name__ == '__main__':
    H,W = [int(i) for i in input().split()]
    ans_list = []
    answer(H,W,ans_list)
    answer(W,H,ans_list)

    print(min(ans_list))

Submission status: Accepted

Solution code:
def answer(H,W,ans):

    for x in range(1,W):
        y1 = H // 2
        Sa1 = H * x
        Sb1 = (W - x) * y1
        Sc1 = (W - x) * (H - y1)
        M = max(Sa1,Sb1,Sc1)
        m = min(Sa1,Sb1,Sc1)

        y2 = (W - x) // 2
        Sa2 = H * x
        Sb2 = H * y2
        Sc2 = H * (W - x - y2)
        M2 = max(Sa2,Sb2,Sc2)
        m2 = min(Sa2,Sb2,Sc2)

        if ans > min(M-m,M2-m2):
            ans = min(M-m,M2-m2)

    return ans

if __name__ == '__main__':
    H,W = [int(i) for i in input().split()]
    ans = H * W
    ans = answer(H,W,ans)

    H,W = W,H

    if answer(H,W,ans) < ans:
        ans = answer(H,W,ans)

    print(ans)

Submission status: Accepted

Solution code:
def answer(H,W,ans_kari):

    for x in range(1,W):
        y1 = H // 2
        Sa1 = H * x
        Sb1 = (W - x) * y1
        Sc1 = (W - x) * (H - y1)
        M = max(Sa1,Sb1,Sc1)
        m = min(Sa1,Sb1,Sc1)

        y2 = (W - x) // 2
        Sa2 = H * x
        Sb2 = H * y2
        Sc2 = H * (W - x - y2)
        M2 = max(Sa2,Sb2,Sc2)
        m2 = min(Sa2,Sb2,Sc2)

        if ans_kari > min(M-m,M2-m2):
            ans_kari = min(M-m,M2-m2)

    return ans_kari

if __name__ == '__main__':
    H,W = [int(i) for i in input().split()]
    ans = H * W
    ans = answer(H,W,ans)
    
    H,W = W,H

    if answer(H,W,ans) < ans:
        ans = answer(H,W,ans)

    print(ans)

Submission status: Accepted

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

for x in range(1,W):
    y1 = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y1
    Sc1 = (W - x) * (H - y1)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    y2 = (W - x) // 2
    Sa2 = H * x
    Sb2 = H * y2
    Sc2 = H * (W - x - y2)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

H,W = W,H
for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    y2 = (W - x) // 2
    Sa2 = H * x
    Sb2 = H * y2
    Sc2 = H * (W - x - y2)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)

Submission status: Accepted

Solution code:
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

H,W = LI()

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

ANS = [H,W]
if H % 3 == 1:
    A = [H//3*W,(H-H//3)*(W//2),(H-H//3)*((W+1)//2)]
    ANS.append(max(A)-min(A))
if H % 3 == 2:
    A = [(H+1)//3*W,(H-(H+1)//3)*(W//2),(H-(H+1)//3)*((W+1)//2)]
    ANS.append(max(A)-min(A))
if W % 3 == 1:
    A = [W//3*H,(W-W//3)*(H//2),(W-W//3)*((H+1)//2)]
    ANS.append(max(A)-min(A))
if W % 3 == 2:
    A = [(W+1)//3*H,(W-(W+1)//3)*(H//2),(W-(W+1)//3)*((H+1)//2)]
    ANS.append(max(A)-min(A))

print(min(ANS))

Submission status: Accepted

Solution code:
from math import ceil

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

#候補1 min(a,b)
#候補2
memory1=1000000000000
for i in range(1,b):
    ar1=a*i
    ar2=(b-i)*ceil(a/2)
    ar3=(b-i)*(a//2)
    p=max(ar1,ar2,ar3)-min(ar1,ar2,ar3)
    if p<memory1:
        memory1=p
    else:
        break
#候補3
memory2=1000000000000
for i in range(1,a):
    ar1=b*i
    ar2=(a-i)*ceil(b/2)
    ar3=(a-i)*(b//2)
    p=max(ar1,ar2,ar3)-min(ar1,ar2,ar3)
    if p<memory2:
        memory2=p
    else:
        break

print(min(min(a,b),memory1,memory2))

Submission status: Accepted

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

if H == 2 and W == 2:
    M = 1

if H > 2:
    HH = H // 3
    S1 = HH * W
    HH = H - H // 3
    HHH = HH // 2
    S2 = HHH * W
    HHH = HH - HH // 2
    S3 = HHH * W
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    HH = H // 3
    S1 = HH * W
    WW = W // 2
    S2 = (H - HH) * WW
    WW = W - W // 2
    S3 = (H - HH) * WW
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    HH = H // 3 + 1
    S1 = HH * W
    WW = W // 2
    S2 = (H - HH) * WW
    WW = W - W // 2
    S3 = (H - HH) * WW
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

if W > 2:
    WW = W // 3
    S1 = WW * H
    WW = W - W // 3
    WWW = WW // 2
    S2 = WWW * H
    WWW = WW - WW // 2
    S3 = WWW * H
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    WW = W // 3
    S1 = WW * H
    HH = H // 2
    S2 = (W - WW) * HH
    HH = H - H // 2
    S3 = (W - WW) * HH
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    WW = W // 3 + 1
    S1 = WW * H
    HH = H // 2
    S2 = (W - WW) * HH
    HH = H - H // 2
    S3 = (W - WW) * HH
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

print(M)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    if W % 3 == 0:
        print(0)
    elif H % 3 == 0:
        print(0)
    else:
        ret = MAX
        for h in range(1, H):
            # 横, 横, 横 分割パターン
            hh = (H - h) // 2
            hmin = min(hh * W, (H - h - hh) * W, h * W)
            hmax = max(hh * W, (H - h - hh) * W, h * W)

            # 横, 縦, 縦 分割パターン
            ww = W // 2
            wmin = min((H - h) * (W - ww), (H - h) * ww, h * W)
            wmax = max((H - h) * (W - ww), (H - h) * ww, h * W)

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        for w in range(1, W):
            # 縦, 縦, 縦 分割パターン
            ww = (W - w) // 2
            wmin = min(w * H, (W - w - ww) * H, ww * H)
            wmax = max(w * H, (W - w - ww) * H, ww * H)

            # 縦, 横, 横 分割パターン
            hh = H // 2
            hmin = min(w * H, hh * (W - w), (H - hh) * (W - w))
            hmax = max(w * H, hh * (W - w), (H - hh) * (W - w))

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

H,W = list(map(int,input().split()))
S = H*W
s1 = 0
ans = 10**10
for i in range(1,H):
    s1 += W
    s2 = (H-i)*(W//2)
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    s2 = ((H-i)//2)*W
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

s1 = 0
for i in range(1,W):
    s1 += H
    s2 = (W-i)*(H//2)
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    s2 = ((W-i)//2)*H
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
stand=h*w/3
prevh,prevw=1,1
mini=10**18
for i in range(2,h+1):
    if abs(stand-i*w)<abs(stand-prevh*w):
        prevh=i
if h-prevh>=2:
    mini=min(mini,max((h-prevh)//2*w,prevh*w,-(-(h-prevh)//2)*w)-min((h-prevh)//2*w,prevh*w,-(-(h-prevh)//2)*w))
mini=min(mini,max(w//2*(h-prevh),prevh*w,-(-w//2)*(h-prevh))-min(w//2*(h-prevh),prevh*w,-(-w//2)*(h-prevh)))
#print(mini)
for i in range(2,w+1):
    if abs(stand-i*h)<abs(stand-prevw*h):
        prevw=i
if w-prevw>=2:
    mini=min(mini,max((w-prevw)//2*h,prevw*h,-(-(w-prevw)//2)*h)-min((w-prevw)//2*h,prevw*h,-(-(w-prevw)//2)*h))
mini=min(mini,max(h//2*(w-prevw),prevw*h,-(-h//2)*(w-prevw))-min(h//2*(w-prevw),prevw*h,-(-h//2)*(w-prevw)))
print(mini)

Submission status: Accepted

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

ans = []

for h in range(1, H):
    r1 = h * W

    h = H - h

    r2a = h // 2 * W
    r3a = -1 * (-h // 2) * W
    r2b = W // 2 * h
    r3b = -1 * (-W // 2) * h

    ans.append(max(r1, r2a, r3a) - min(r1, r2a, r3a))
    ans.append(max(r1, r2b, r3b) - min(r1, r2b, r3b))

for w in range(1, W):
    r1 = H * w

    w = W - w

    r2a = H // 2 * w
    r3a = -1 * (-H // 2) * w
    r2b = w // 2 * H
    r3b = -1 * (-w // 2) * H

    ans.append(max(r1, r2a, r3a) - min(r1, r2a, r3a))
    ans.append(max(r1, r2b, r3b) - min(r1, r2b, r3b))

print(min(ans))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()

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

def divide_3(a, b):
    diff1, diff2 = INF, INF
    for i in range(-1, 2):
        p1 = (a//3+i) * b
        left_1 = H*W - p1
        p2 = b//2 * (a - (a//3+i))
        p3 = left_1 - p2
        diff_1 = max(p1, p2, p3) - min(p1, p2, p3)
        diff1 = min(diff1, diff_1)

        q1 = (ceil(a/3)+i) * b
        left_2 = H*W - q1
        q2 = b//2 * (a - (ceil(a/3)+i))
        q3 = left_2 - q2
        diff_2 = max(q1, q2, q3) - min(q1, q2, q3)
        diff2 = min(diff2, diff_2)

    return min(diff1, diff2, a, b)

print(min(divide_3(H, W), divide_3(W, H)))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
tanpen = min(h, w)
chohen = max(h, w)

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    def findmin(h, w):
        ans = h*w
        for i in range(1, h):
            remi = h - i
            s1 = i*w
            s2 = (w//2) * remi
            s3 = (w - w//2) * remi
            ans = min(ans, max(s1, s2, s3) - min(s1, s2))

            s2 = w * (remi//2)
            s3 = w * (remi - remi//2)
            ans = min(ans, max(s1, s2, s3) - min(s1, s2))
        return ans
    print(min(findmin(h, w), findmin(w, h)))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W = getNM()

res = 0
# 縦縦
opt1 = float('inf')
if W % 3 == 0:
    opt1 = 0
else:
    opt1 = H

# 縦横
opt2 = float('inf')
for i in range(1, W + 1):
    opt_a = i * H
    opt_b = (W - i) * (H // 2)
    opt_c = H * W - opt_a - opt_b
    opt = max(opt_a, opt_b, opt_c) - min(opt_a, opt_b, opt_c)
    opt2 = min(opt2, opt)

# 横横
opt3 = float('inf')
if H % 3 == 0:
    opt3 = 0
else:
    opt3 = W

# 横縦
opt4 = float('inf')
for i in range(1, H + 1):
    opt_a = i * W
    opt_b = (H - i) * (W // 2)
    opt_c = H * W - opt_a - opt_b
    opt = max(opt_a, opt_b, opt_c) - min(opt_a, opt_b, opt_c)
    opt4 = min(opt4, opt)

print(min(opt1, opt2, opt3, opt4))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc(x, y):
        ans = INF
        area = x * y
        for i in range(1, x):
            first = y * i
            x_rem = x - i
            rem = area - first
            if x_rem % 2 == 0 or y % 2 == 0:
                second = rem // 2
                third = rem // 2
            else:
                second = min(x_rem, y) * (max(x_rem, y) // 2 + 1)
                third = rem - second
            score = max(first, second, third) - min(first, second, third)
            ans = min(ans, score)
        return ans

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

    if h % 3 == 0 or w % 3 == 0:
        print(0)
    else:
        ans = min(calc(h, w), calc(w, h))
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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

    pattern = [h, w]
    for x in range(1, w//2 + 2):
        first = x * h
        h1 = h // 2
        h2 = h - h1
        second = (w-x) * h1
        thrid = (w-x) * h2
        result = max(first, second, thrid) - min(first, second, thrid)
        pattern.append(result)

    for y in range(1, h//2 + 2):
        first = y * w
        w1 = w // 2
        w2 = w - w1
        second = (h-y) * w1
        thrid = (h-y) * w2
        result = max(first, second, thrid) - min(first, second, thrid)
        pattern.append(result)

    print(min(pattern))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

A=0
B=0
ans=H*W

if H%2==0:
  A=H//2
  B=H//2
else:
  A=H//2+1
  B=H-A
for i in range(1,W):
  S1=A*i
  S2=B*i
  S3=(W-i)*H
  SMaxMin=max(S1,S2,S3)-min(S1,S2,S3)
  ans=min(ans,SMaxMin)
if W%2==0:
  A=W//2
  B=W//2
else:
  A=W//2+1
  B=W-A;
for i in range(1,H):
  S1=A*i
  S2=B*i
  S3=(H-i)*W
  SMaxMin=max(S1,S2,S3)-min(S1,S2,S3)
  ans=min(ans,SMaxMin)
if H>=3:
  ans=min(ans,W)
if W>=3:
  ans=min(ans,H)
print(ans)

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")
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    if (h%3==1):
        ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    else:
        ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
ans = min(ans,w)
    
a = w
w = h
h = a
#print(h,w)
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    if (h%3==1):
        ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    else:
        ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
ans = min(ans,w)
    
print(ans)

Submission status: Accepted

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

tmps = 0
ans = 10**18
for i in range(1,h):
	k = (h-i)//2
	t = [i*w, k*w, (h-i-k)*w]
	tmp = max(t)-min(t)
	ans = min(tmp, ans)
	k = w//2
	t = [i*w, (h-i)*k, (h-i)*(w-k)]
	tmp = max(t)-min(t)
	ans = min(tmp, ans)
for i in range(1,w):
	k = (w-i)//2
	t = [i*h, k*h, (w-i-k)*h]
	tmp = max(t)-min(t)
	ans = min(tmp, ans)
	k = h//2
	t = [i*h, (w-i)*k, (w-i)*(h-k)]
	tmp = max(t)-min(t)
	ans = min(tmp, ans)
print(ans)

Submission status: Accepted

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

h = min(H, W)
w = max(H, W)
s = h*w

res = 10**10

for i in range(1, w):
    a = h*i
    b = (w-i)//2*h
    c = s-a-b
    res = min(max(a, b, c)-min(a, b, c), res)

    b = (w-i)*(h//2)
    c = s-a-b
    res = min(max(a, b, c)-min(a, b, c), res)


for i in range(1, h):
    a = w*i
    
    b = (h-i)//2*w
    c = s-a-b
    res = min(max(a, b, c)-min(a, b, c), res)

    b = (h-i)*(w//2)
    c = s-a-b
    res = min(max(a, b, c)-min(a, b, c), res)

print(res)

Submission status: Accepted

Solution code:
def divide_into_three(X, Y):
    minimum = float("inf")
    for x in range(1, X):
        b1 = x * Y
        if not all(((X - x) & 1, Y & 1)):
            b2 = b3 = ((X - x) * Y) >> 1
        else:
            s, l = sorted((X - x, Y))
            b2 = s * (l >> 1)
            b3 = s * l - b2
        diff = max((b1, b2, b3)) - min((b1, b2, b3))
        minimum = min(minimum, diff)
    return minimum

H, W = map(int, input().split())
print(min(divide_into_three(H, W), divide_into_three(W, H)))

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    h,w=map(int,readline().split())

    if h*w%3==0:
        ans=0
    else:
        ans=float("inf")
        #縦方向に全探索
        s1=w//2*h
        s2=h*w-s1
        for i in range(1,h):
            s3=i*w
            s1-=w//2
            s2-=w-w//2
            ans=min(ans,max(s1,s2,s3)-min(s1,s2,s3))

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

        #横方向に全探索
        s1=h//2*w
        s2=h*w-s1
        for j in range(1,w):
            s3=j*h
            s1-=h//2
            s2-=h-h//2
            ans=min(ans,max(s1,s2,s3)-min(s1,s2,s3))
        
        for j in range(1,w-1):
            s3=j*h
            s1=(w-j)//2*h
            s2=h*w-s3-s1
            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=min(h,w)
if h%3==0 or w%3==0:
  print(0)
  exit(0)
for hi in range(1,h):
  mi=min(w*hi,w//2*(h-hi),(w-w//2)*(h-hi))
  ma=max(w*hi,w//2*(h-hi),(w-w//2)*(h-hi))
  ans=min(ans,ma-mi)
for wi in range(1,w):
  mi=min(h*wi,h//2*(w-wi),(h-h//2)*(w-wi))
  ma=max(h*wi,h//2*(w-wi),(h-h//2)*(w-wi))
  ans=min(ans,ma-mi)
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ans = min(w, h)
    for w1 in range(w//3, w//3+3):
        s1 = w1 * h
        w2 = w-w1
        for h1 in range(h//2, h//2+2):
            s2 = w2 * h1
            s3 = w2 * (h-h1)
            ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    h, w = w, h
    for w1 in range(w//3, w//3+3):
        s1 = w1 * h
        w2 = w-w1
        for h1 in range(h//2, h//2+2):
            s2 = w2 * h1
            s3 = w2 * (h-h1)
            ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    if h > w:
        h, w = w, h
    ans = h
    for w1 in range(w//3-2, w//3+3):
        s1 = w1 * h
        w2 = w-w1
        for h1 in range(h//2 + 1):
            s2 = w2 * h1
            s3 = w2 * (h-h1)
            ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    h, w = w, h
    for w1 in range(w//3-2, w//3+3):
        s1 = w1 * h
        w2 = w-w1
        for h1 in range(h//2 + 1):
            s2 = w2 * h1
            s3 = w2 * (h-h1)
            ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split());print(min(min(min(max((i*w,(h-i)//2*w,(h-i-(h-i)//2)*w))-min((i*w,(h-i)//2*w,(h-i-(h-i)//2)*w)),max((i*w,w//2*(h-i),(h-i)*(w-w//2)))-min((i*w,w//2*(h-i),(h-i)*(w-w//2))))for i in range(h)),min(min(max((h*i,(w-i)//2*h,h*(w-i-(w-i)//2)))-min((h*i,(w-i)//2*h,h*(w-i-(w-i)//2))),max((h*i,h//2*(w-i),(h-h//2)*(w-i)))-min((h*i,h//2*(w-i),(h-h//2)*(w-i))))for i in range(w))))

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    d = h * w
    for i in range(1, h):
        sh = (h - i) // 2
        s = (i * w, sh * w, (h - i - sh) * w)
        d = min(max(s) - min(s), d)
        sv = w // 2
        s = (i * w, (h - i) * sv, (h - i) * (w - sv))
        d = min(max(s) - min(s), d)
    for i in range(1, w):
        sv = (w - i) // 2
        s = (h * i, h * sv, h * (w - i - sv))
        d = min(max(s) - min(s), d)
        sh = h // 2
        s = (h * i, sh * (w - i), (h - sh) * (w - i))
        d = min(max(s) - min(s), d)
    print(d)


if __name__ == '__main__':
    main()