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())

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

res = min(h,w)
for hi in range(1,h):
    b1 = hi*w
    b2 = (h-hi)*(w//2)
    b3 = (h-hi)*(w//2+w%2)
    res = min(res, max(b1,b2,b3)-min(b1,b2,b3))
for wi in range(1,w):
    b1 = wi*h
    b2 = (w-wi)*(h//2)
    b3 = (w-wi)*(h//2+h%2)
    res = min(res, max(b1,b2,b3) - min(b1,b2,b3))

print(res)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
def f(x,y):
    ret=(1 if x%3 else 0)*y
    for i in range(1,x):
        f=sorted((i*y,y//2*(x-i),(1+y)//2*(x-i)))
        ret=min(ret,f[2]-f[0])
    return ret
print(min(f(h,w),f(w,h)))

Submission status: Accepted

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

def f():
    if H % 3 == 0:
        return 0
    else:
        r = W
    
    for i in range(1, H):
        s1 = i * W
        if W % 2 == 0:
            s2 = s3 = (H - i) * (W // 2)
        else:
            s2 = (H - i) * (W // 2)
            s3 = (H - i) * (W - W // 2)
        r = min(r, max(s1, s2, s3) - min(s1, s2, s3))
    
    return r

res = f()
H, W = W, H
res = min(res, f())
print(res)

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
if H == 1 or W == 1:
    print(1)
    exit()
ans = 1 << 30
w = W//2
for h in range(1, H+1):
    s1 = w*h
    s2 = (W-w)*h
    s3 = W*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
W, H = H, W
w = W//2
for h in range(1, H+1):
    s1 = w*h
    s2 = (W-w)*h
    s3 = W*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
ans = min(ans, H, W)
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = 10**18
for i in range(1, h):
    S1 = i*w
    # tate
    if h-i >= 2:
        p = (h-i)//2
        q = h-(h-i)//2-i
        S2 = p*w
        S3 = q*w
        M = max([S1, S2, S3])
        m = min([S1, S2, S3])
        ans = min(ans, M-m)
        #if i == 1:
            #print(S1, S2, S3)
    # yoko
    S2 = (h-i)*(w//2)
    S3 = (h-i)*(w-w//2)
    M = max([S1, S2, S3])
    m = min([S1, S2, S3])
    ans = min(ans, M-m)

for i in range(1, w):
    S1 = h*i
    # yoko
    if w-i >= 2:
        p = (w-i)//2
        q = w-(w-i)//2-i
        S2 = h*p
        S3 = h*q
        M = max([S1, S2, S3])
        m = min([S1, S2, S3])
        ans = min(ans, M-m)
    # tate
    S2 = (h//2)*(w-i)
    S3 = (h-h//2)*(w-i)
    M = max([S1, S2, S3])
    m = min([S1, S2, S3])
    ans = min(ans, M-m)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**9
if h%3==0 or w%3==0:
  ans=0
ans=min(ans,w)
ans=min(ans,h)
for i in range(w//3,min((w//3+4),w)):
  m=[]
  m.append(i*h)
  m.append((w-i)*(h//2))
  m.append((w-i)*(h-(h//2)))
  m.sort()
  ans=min(ans,m[2]-m[0])
for i in range(h//3,min((h//3+4),h)):
  m=[]
  m.append(i*w)
  m.append((h-i)*(w//2))
  m.append((h-i)*(w-(w//2)))
  m.sort()
  ans=min(ans,m[2]-m[0])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

    for i in range(1, H):
        S1 = i*W
    
        if W%2==0:
            S2 = (H-i)*(W//2)
            S3 = (H-i)*(W//2)
        else:
            S2 = (H-i)*(W//2)
            S3 = (H-i)*(W-W//2)
    
        ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))
    
H, W = map(int, input().split())
ans = 10**18
f()
H, W = W, H
f()
print(ans)

Submission status: Accepted

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

ans = float("inf")
for i in range(1, H):
    h = H - i
    s1 = [i * W, h // 2 * W, (h - h // 2) * W]
    if 0 not in s1: ans = min(ans, max(s1)-min(s1))
    s2 = [i * W, W // 2 * h, (W - W // 2) * h]
    if 0 not in s2: ans = min(ans, max(s2) - min(s2))

for i in range(1, W):
    w = W - i
    s1 = [i * H, w // 2 * H, (w - w // 2) * H]
    if 0 not in s1: ans = min(ans, max(s1)-min(s1))
    s2 = [i * H, H // 2 * w, (H - H // 2) * w]
    if 0 not in s2: ans = min(ans, max(s2) - min(s2))

print(ans)

Submission status: Accepted

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


def solve_ll(a, b):
    x, y = divmod(a, 3)
    X = [x]*3
    for i in range(y):
        X[i] += 1
    s1, s2, s3 = map(lambda x: x*b, X)
    return s1-s3


def solve_T(a, b):
    INF = 10**18
    res = INF
    for x in (b//3, -(-b//3)):
        s1 = x*a
        y = b-x
        x1, x2 = a//2, (a+1)//2
        s2, s3 = x1*y, x2*y
        Ss = (s1, s2, s3)
        res = min(res, max(Ss)-min(Ss))
    return res


ans = min(solve_T(h, w), solve_T(w, h), solve_ll(h, w), solve_ll(w, h))
print(ans)

Submission status: Accepted

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

# =パターン
x, y = divmod(h, 3)
if y == 0:
    x1, x2, x3 = x, x, x
elif y == 1:
    x1, x2, x3 = x+1, x, x
else:
    x1, x2, x3 = x+1, x+1, x

s1, s2, s3 = map(lambda x: x*w, (x1, x2, x3))
ans = s1-s3

# llパターン
x, y = divmod(w, 3)
if y == 0:
    x1, x2, x3 = x, x, x
elif y == 1:
    x1, x2, x3 = x+1, x, x
else:
    x1, x2, x3 = x+1, x+1, x

s1, s2, s3 = map(lambda x: x*h, (x1, x2, x3))
ans = min(ans, s1-s3)

# トパターン
x = -(-w//3)
s1 = x*h
y = w-x
x1, x2 = h//2, (h+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# トパターン
x = w//3
s1 = x*h
y = w-x
x1, x2 = h//2, (h+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# Tパターン
x = -(-h//3)
s1 = x*w
y = h-x
x1, x2 = w//2, (w+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# Tパターン
x = h//3
s1 = x*w
y = h-x
x1, x2 = w//2, (w+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))
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(h,w)
    for i in range(1,h):
        if w % 2 == 0:
            ans = min(ans,max(w*i,(h-i)*(w//2)) - min(w*i,(h-i)*(w//2)))
        elif w % 2 == 1:
            ans = min(ans,max(w*i,(h-i)*(w//2),(h-i)*(w//2+1)) - min(w*i,(h-i)*(w//2),(h-i)*(w//2+1)))
    for i in range(1,w):
        if h % 2 == 0:
            ans = min(ans,max(h*i,(w-i)*(h//2)) - min(h*i,(w-i)*(h//2)))
        elif h % 2 == 1:
            ans = min(ans,max(h*i,(w-i)*(h//2),(w-i)*(h//2+1)) - min(h*i,(w-i)*(h//2),(w-i)*(h//2+1)))
    print(ans)

Submission status: Accepted

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

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

S = H * W
a = (S // 3 // H) - 10
b = (S // 3 // W) - 10

ans1 = float('inf')
ans2 = float('inf')
for i in range(a, a + 30):
    if i <= 0 or i >= W:
        continue
    x = i * H
    y = (W - i) * (H//2)
    z = S - x - y
    ans1 = min(ans1, max(x, y, z) - min(x, y, z))

for i in range(b, b + 30):
    if i <= 0 or i >= H:
        continue
    x = i * W
    y = (H - i) * (W//2)
    z = S - x - y
    ans2 = min(ans2, max(x, y, z) - min(x, y, z))
print(min(ans1, ans2, H, W))

Submission status: Accepted

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

h,w=min(h,w),max(h,w)
ans=float('inf')
for i in range(1,w):
    s1=h*i
    neww=w-i
    newh,neww=min(h,neww),max(h,neww)
    if newh%2==0 or neww%2==0:
        s2=(newh*neww)//2
        s3=first-(s1+s2)
        s4=(newh*neww)//2
        s5=first-(s1+s2)
    else:
        s2=newh*(neww//2)
        s3=first-(s1+s2)
        s4=(newh//2)*neww
        s5=first-(s1+s4)
    #print(s1,s2,s3)
    ans=min(ans,max([s1,s2,s3])-min([s1,s2,s3]), max([s1,s4,s5])-min([s1,s4,s5]))

for i in range(1,h):
    s1=w*i
    newh=h-i
    newh,neww=min(newh,w),max(newh,w)
    if newh%2==0 or neww%2==0:
        s2=(newh*neww)//2
        s3=first-(s1+s2)
        s4=(newh*neww)//2
        s5=first-(s1+s2)
    else:
        s2=newh*(neww//2)
        s3=first-(s1+s2)
        s4=(newh//2)*neww
        s5=first-(s1+s4)
    #print(s1,s2,s3)
    ans=min(ans,max([s1,s2,s3])-min([s1,s2,s3]), max([s1,s4,s5])-min([s1,s4,s5]))

print(ans)

Submission status: Accepted

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

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

hh=h//2
ww=w//2
hhh=-(-h//3)
www=-(-w//3)
a=www*h
b=hh*(w-www)
c=h*w-a-b
L=max(abs(a-b),abs(b-c),abs(c-a))
a=hhh*w
b=ww*(h-hhh)
c=h*w-a-b
R=max(abs(a-b),abs(b-c),abs(c-a))
hhh=h//3
www=w//3
a=www*h
b=hh*(w-www)
c=h*w-a-b
U=max(abs(a-b),abs(b-c),abs(c-a))
a=hhh*w
b=ww*(h-hhh)
c=h*w-a-b
D=max(abs(a-b),abs(b-c),abs(c-a))
T=min(T,L,R,U,D)
print(T)

Submission status: Accepted

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


def f(H, W):
    mh = H // 2
    if mh != 0:
        yield mh*W, (H-mh)*W
    mw = W // 2
    if mw != 0:
        yield H*mw, H*(W-mw)

def solve_iter(H: int, W: int):
    for h in range(1, H):
        for s in (tuple([h*W])+s for s in f(H-h, W)):
            yield max(s) - min(s)
    for w in range(1, W):
        for s in (tuple([H*w])+s for s in f(H, W-w)):
            yield max(s) - min(s)

def solve(H: int, W: int):
    return min(solve_iter(H, W))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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
    print(solve(H, W))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if (h%3)*(w%3)==0:
    print(0)
    exit(0)
def solve(a, b):
    ans = 10**10
    s1 = a*(b//3)
    s2 = (a//2)*(b-b//3)
    s3 = ((a+1)//2)*(b-b//3)
    s4 = a*((b+2)//3)
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
    ans = min(ans, max(s1, s4)-min(s1, s4))
    s1 = a*((b+2)//3)
    s2 = (a//2)*(b-(b+2)//3)
    s3 = ((a+1)//2)*(b-(b+2)//3)
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
    return ans
print(min(solve(h, w), solve(w, h)))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc074/tasks/arc074_a

from math import floor


def solve(H, W):
    # hの全探索
    ans = 10 ** 10
    for h in range(1, H):
        SA = h * W

        # (1) A-B-C 均等割
        dh = floor((H - h) / 2)
        SB = dh * W
        SC = (H - h - dh) * W
        a1 = max(SA, SB, SC) - min(SA, SB, SC)
        ans = min(ans, a1)

        # (2) A-B|C
        w = floor(W / 2)
        SB = (H - h) * w
        SC = (H - h) * (W - w)
        a2 = max(SA, SB, SC) - min(SA, SB, SC)
        ans = min(ans, a2)
    return ans


if __name__ == '__main__':
    h, w = map(int, input().split())
    ans1 = solve(h, w)
    ans2 = solve(w, h)
    print(min(ans1, ans2))

Submission status: Accepted

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

s = h * w

ts = s / 3
ans = s
ps = [s, 0, 0]

for pattern in range(4):
    p = list(bin(pattern)[2:].zfill(2))
    p = [int(_p) for _p in p]
    size = [h, w]
    ps = [s, 0, 0]
    for i, f in enumerate(p):
        df = round(ts / size[f ^ 1])
        ps[i + 1] = ps[i] - df * size[f ^ 1]
        ps[i] = df * size[f ^ 1]
        size[f] -= df
    ans = min(ans, max(ps)-min(ps))

print(ans)

Submission status: Accepted

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

def Divisions(a, b):
    if a % 3 == 0:
        return 0
    else:
        cnt = b
        for i in range(a+1):
            s = min(i * b, (a - i) * (b // 2))
            l = max(i * b, (a - i) * (b - b // 2))
            cnt = min(cnt, l - s)
        return cnt

print(min(Divisions(h, w), Divisions(w, h)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**9

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

a=h//2
b=h-a
for i in range(1,w):
    length=w-i
    A=i*a
    B=i*b
    peace_max=max(length*h,A,B)
    peace_min=min(length*h,A,B)
    ans=min(ans,peace_max-peace_min)

a=w//2
b=w-a
for i in range(1,h):
    length=h-i
    A=i*a
    B=i*b
    peace_max=max(length*w,A,B)
    peace_min=min(length*w,A,B)
    ans=min(ans,peace_max-peace_min)

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

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 = float('inf')
    for h in range(1, H):
        dh = H-h
        Sa = h*W
        Sb = dh*(W//2)
        Sc = dh*(W//2+W%2)
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
        Sb = dh//2*W
        Sc = (dh//2+dh%2)*W
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
    
    for w in range(1, W):
        dw = W-w
        Sa = w*H
        Sb = dw*(H//2)
        Sc = dw*(H//2+H%2)
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
        Sb = dw//2*H
        Sc = (dw//2+dw%2)*H
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        exit()
    if H == 2 or W == 2:
        print(1)
        exit()

    lh, gh = H // 3, H // 3 + 1
    lw, gw = W // 3, W // 3 + 1

    ans = min(H, W)

    a = lh * W
    b, c = (H - lh) * (W // 2), (H - lh) * (W - W // 2)
    gap = max(a,b,c) - min(a,b,c)
    ans = min(ans, gap)

    a = gh * W
    b, c = (H - gh) * (W // 2), (H - gh) * (W - W // 2)
    gap = max(a,b,c) - min(a,b,c)
    ans = min(ans, gap)

    a = H * lw
    b, c = (W - lw) * (H // 2), (W - lw) * (H - H // 2)
    gap = max(a,b,c) - min(a,b,c)
    ans = min(ans, gap)

    a = H * gw
    b, c = (W - gw) * (H // 2), (W - gw) * (H - H // 2)
    gap = max(a,b,c) - min(a,b,c)
    ans = min(ans, gap)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
  h, w = map(int, input().split())  
  if h%3 == 0 or w%3 == 0:
    print(0)
  elif h == 1 or w == 1:
    print(1)
  else:
    def f(h, w):
      y = h//2
      x = 2 * (w // 3)
      score = 10**9
      for dx in range(2):
        cands = [(x+dx)*y, (x+dx)*(h-y), (w - (x+dx))*h]
        score = min(score, max(cands) - min(cands))
      return score
    print(min([f(h, w), f(w, h), h, w]))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from math import ceil, floor

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    def calc_diff_a(h, w):
        a = ceil(h / 3) * w
        b = (h - ceil(h / 3)) * floor(w / 2)
        c = (h - ceil(h / 3)) * ceil(w / 2)
        diff = max(a, b, c) - min(a, b, c)
        a = floor(h / 3) * w
        b = (h - floor(h / 3)) * floor(w / 2)
        c = (h - floor(h / 3)) * ceil(w / 2)
        diff = min(diff, max(a, b, c) -min(a, b,c))
        return diff
    def calc_diff_b(h, w):
        a = ceil(h / 3) * w
        b = floor((h - ceil(h / 3)) / 2) * w
        c = ceil((h - ceil(h / 3)) / 2) * w
        diff = max(a, b, c) - min(a, b, c)
        a = floor(h / 3) * w
        b = floor((h - floor(h / 3)) / 2) * w
        c = ceil((h - floor(h / 3)) / 2) * w
        diff = min(diff, max(a, b, c) - min(a, b, c))
        return diff

    print(min(calc_diff_a(h, w), calc_diff_a(w, h), calc_diff_b(h, w), calc_diff_b(w, h)))

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#28-

n,m= list(map(int, input().split()))
ans = 10**9

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

if(n%3==0 or m%3==0):
    ans = 0
else:
    ans = min(ans,n,m)
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

    def calc(h, w):
        ret = 10 ** 10
        for r1 in range(1, h):
            ma = max(r1, h - r1)

            r2 = ma // 2
            r3 = ma - r2

            ret = min(ret, (max(r1, r2, r3) - min(r1, r2, r3)) * w)

            c2 = w // 2
            c3 = w - c2

            s1 = r1 * w
            s2 = ma * c2
            s3 = ma * c3
            ret = min(ret, max(s1, s2, s3) - min(s1, s2, s3))
        return ret

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

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

Submission status: Accepted

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

if H%3==0 or W%3==0:
    print(0)
else:
    vals = []
    if H>=3:
        vals.append((H//3+1)*W-(H//3)*W)
    for i in range(3):
        x = (W//3+i)*H
        vals.append(max(abs(x-(W-W//3-i)*(H//2)), abs((W-W//3-i)*(H//2)-(W-W//3-i)*(H//2+H%2)), abs(x-(W-W//3-i)*(H//2+H%2))))

    H, W = W, H
    if H>=3:
        vals.append((H//3+1)*W-(H//3)*W)
    for i in range(3):
        x = (W//3+i)*H
        vals.append(max(abs(x-(W-W//3-i)*(H//2)), abs((W-W//3-i)*(H//2)-(W-W//3-i)*(H//2+H%2)), abs(x-(W-W//3-i)*(H//2+H%2))))
    print(min(vals))

Submission status: Accepted

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

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

ans = min(H, W)
for A, B in ((H, W), (W, H)):
    for a in (A // 3, A // 3 + 1):
        for b in (B // 2, B // 2 + 1):
            X = a * B
            Y = (A - a) * b
            Z = (A - a) * (B - b)

            ans = min(ans, max(X, Y, Z) - min(X, Y, Z))
print(ans)

Submission status: Accepted

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

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

ans = float("inf")  
if W < H:
  W,H = H,W
  
for i in range(1,W): #W>=Hの前提で考える。
  a = H*i
  if H%2 == 0:
    b = (W-i)*(H//2)
    ans = min(ans,abs(a-b))
  else:
    b = (W-i)*(H//2)
    c = (W-i)*(H//2+1)
    dif = max(abs(a-b),abs(a-c),abs(b-c))
    ans = min(ans,dif)

for i in range(1,H): #W>=Hの前提で考える。
  a = W*i
  if W%2 == 0:
    b = (H-i)*(W//2)
    ans = min(ans,abs(a-b))
  else:
    b = (H-i)*(W//2)
    c = (H-i)*(W//2+1)
    dif = max(abs(a-b),abs(a-c),abs(b-c))
    ans = min(ans,dif)    

#横分割
ans = min(ans,H)
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
if (H*W)%3==0:
    dif = 0
else:
    dif = min(H,W)
    for i in range(1,W//2+1):
        s1 = H*i
        s2 = (W-i)*(H//2)
        s3 = (W-i)*(H-H//2)
        d = max(s1,s2,s3)-min(s1,s2,s3)
        dif = min(dif,d)
    for j in range(1,H//2+1):
        s1 = W*j
        s2 = (H-j)*(W//2)
        s3 = (H-j)*(W-W//2)
        d = max(s1,s2,s3)-min(s1,s2,s3)
        dif = min(dif,d)
print(dif)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    H,W=pin()

    if H%3==0 or W%3==0:
        print(0)
        return
    #     
    ans=min(H,W)
    for i in range(1,H):
        yoko=W*i
        a=W//2*(H-i)
        b=W*H-yoko-a
        
        t=(max(yoko,a,b)-min(yoko,a,b))
        ans=min(t,ans)

    for j in range(1,W):
        yoko=H*j
        a=(H//2)*(W-j)
        b=W*H-yoko-a
        
        t=(max(yoko,a,b)-min(yoko,a,b))
        ans=min(t,ans)
    print(ans)
#%%submit!
resolve()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = float("inf")

Hh = [H//2,H//2+1]
Wh = [W//2,W//2+1]
Ht = [H//3,H//3+1]
Wt = [W//3,W//3+1]

for i in Ht:
  for j in Ht:
    k = H -i -j
    ans = min(ans,W*(max(i,j,k)-min(i,j,k)))
for i in Wt:
  for j in Wt:
    k = W -i -j
    ans = min(ans,H*(max(i,j,k)-min(i,j,k)))

for i in Ht:
  b = H-i
  for j in Wh:
    k = W-j
    ans = min(ans, max(W*i,b*j,b*k)-min(W*i,b*j,b*k))
for i in Wt:
  b = W-i
  for j in Hh:
    k = H-j
    ans = min(ans, max(H*i,b*j,b*k)-min(H*i,b*j,b*k))
###
print(ans)

Submission status: Accepted

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

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

ans = H * W

if H % 3 == 0:
    ans = 0
elif H >= 4:
    ans = min(ans, W)

if W % 3 == 0:
    ans = 0
elif W >= 4:
    ans = min(ans, H)

for h in range(1, H):
    tmp1 = W * h
    tmp2 = (H - h) * (W // 2)
    tmp3 = (H - h) * ((W + 1) // 2)
    tmp_ans = max(tmp1, tmp3) - min(tmp1, tmp2)
    ans = min(ans, tmp_ans)

H, W = W, H
for h in range(1, H):
    tmp1 = W * h
    tmp2 = (H - h) * (W // 2)
    tmp3 = (H - h) * ((W + 1) // 2)
    tmp_ans = max(tmp1, tmp3) - min(tmp1, tmp2)
    ans = min(ans, tmp_ans)

    
print (ans)

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int, input().split())
    if H*W%3==0:
        return 0
    if H%2==0 and W%2==0:
        return min(H//2,W//2)
    if H%2==0:
        return min([H//2,H//3*2+W//2+1-min(H//3,W//2),W])
    if W%2==0:
        return min([W//2,W//3*2+H//2+1-min(W//3,H//2),H])
    return min([H//3*2+W//2+1-min(H//3,W//2),W//3*2+H//2+1-min(W//3,H//2),H,W])
print(solve())

Submission status: Accepted

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

ans = []

if H > 2:
    ans.append(W*max(H//3, (H-H//3)//2, H-H//3-(H-H//3)//2)-W*min(H//3, (H-H//3)//2, H-H//3-(H-H//3)//2))
if W > 2:
    ans.append(H*max(W//3, (W-W//3)//2, W-W//3-(W-W//3)//2)-H*min(W//3, (W-W//3)//2, W-W//3-(W-W//3)//2))

num = 10**10
for x in range(1, W):
    num = min(num, max(H*x, (W-x)*(H//2), (W-x)*(H-H//2))-min(H*x, (W-x)*(H//2), (W-x)*(H-H//2)))
ans.append(num)
num = 10**10
for x in range(1, H):
    num = min(num, max(W*x, (H-x)*(W//2), (H-x)*(W-W//2))-min(W*x, (H-x)*(W//2), (H-x)*(W-W//2)))
ans.append(num)
print(min(ans))

Submission status: Accepted

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

ans = min(H,W)

for _ in range(2):
    for i in range(1,W):
        a = H*i
        m = H//2
        b = m*(W-i)
        c = (H-m)*(W-i)
        mx = max(a,b,c)
        mn = min(a,b,c)
        ans = min(ans, mx-mn)
    H,W = W,H
print(ans)

Submission status: Accepted

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

def divide(h,w):
    h,w = max(h,w),min(h,w)
    if h%2 and w%2:
        ret = [h//2*w, (h+1)//2*w]
    else:
        ret = [h*w//2, h*w//2]
    return ret

ans = 10**12

for i in range(1,H+1):
    s = [W*i] + divide(H-i,W)
    ans = min(ans,max(s)-min(s))
H,W = W,H
for i in range(1,H+1):
    s = [W*i] + divide(H-i,W)
    ans = min(ans,max(s)-min(s))
print(ans)

Submission status: Accepted

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

out = H*W

for Hi in range(1,H):
    S1 = W*Hi
    Hr = H-Hi
    S2a = (W//2)*Hr
    S3a = (W-W//2)*Hr
    S2b = W*(Hr//2)
    S3b = W*(Hr - (Hr//2))
    Da = max(S1,S2a,S3a)-min(S1,S2a,S3a)
    Db = max(S1,S2b,S3b)-min(S1,S2b,S3b)
    cand = min(Da,Db)
    if cand<out:
        out=cand
for Wi in range(1,W):
    S1 = Wi*H
    Wr = W-Wi
    S2a = (H//2)*Wr
    S3a = (H-H//2)*Wr
    S2b = H*(Wr//2)
    S3b = H*(Wr - (Wr//2))
    Da = max(S1,S2a,S3a)-min(S1,S2a,S3a)
    Db = max(S1,S2b,S3b)-min(S1,S2b,S3b)
    cand = min(Da,Db)
    if cand<out:
        out=cand
print(out)

Submission status: Accepted

Solution code:
import math
h,w = map(int,input().split())
if h*w%3 == 0:
    print(0)
    exit()
mi = 10**18

hi = h
wi = w
s = [wi*(hi//3),0,0]
hi = h-h//3
s[1],s[2] = wi*(hi//2),wi*math.ceil(hi/2)
mi = min(mi,max(s)-min(s))
s[1],s[2] = hi*(wi//2),hi*math.ceil(wi/2)
mi = min(mi,max(s)-min(s))

hi = h
wi = w
s = [wi*math.ceil(hi/3),0,0]
hi = h-math.ceil(h/3)
s[1],s[2] = wi*(hi//2),wi*math.ceil(hi/2)
mi = min(mi,max(s)-min(s))
s[1],s[2] = hi*(wi//2),hi*math.ceil(wi/2)
mi = min(mi,max(s)-min(s))

hi = h
wi = w
s = [hi*(wi//3),0,0]
wi = w-w//3
s[1],s[2] = wi*(hi//2),wi*math.ceil(hi/2)
mi = min(mi,max(s)-min(s))
s[1],s[2] = hi*(wi//2),hi*math.ceil(wi/2)
mi = min(mi,max(s)-min(s))

hi = h
wi = w
s = [hi*math.ceil(wi/3),0,0]
wi = w-math.ceil(w/3)
s[1],s[2] = wi*(hi//2),wi*math.ceil(hi/2)
mi = min(mi,max(s)-min(s))
s[1],s[2] = hi*(wi//2),hi*math.ceil(wi/2)
mi = min(mi,max(s)-min(s))

print(mi)

Submission status: Accepted

Solution code:






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

"""
割るとすれば
・縦直線で割ってから縦直線で割る
・縦直線で割ってから横直線で割る
・横直線で割ってから横直線で割る
・横直線で割ってから縦直線で割る

の４パターン
愚直にやると、
それぞれ最初の割り方をどの位置で割るか決めた後、残りのどっちを割るか決めて、選んだ方のどの位置で割るか決める
になるから、H*W*4?みたいな感じになって、まぁとにかく間に合わない。

割り終わった後にできる３つのピースの最大と最小の差をできるだけ小さくしたい、なので、２回目の割り方については、なるべく等分に近くなるように割るのがよい。はず。
"""


ans = H*W

# 先に横直線で割るパターン
for h in range(1,H):
    p1 = W * h
    # 残りも横直線で割る場合
    p2 = ((H-h) // 2) * W
    p3 = H*W - p1 - p2
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

    # 残りを縦で割る
    p2 = (H-h) * (W // 2)
    p3 = H*W - p1 - p2 
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

for w in range(1, W):
    p1 = w*H
    p2 = ((W-w) // 2) * H
    p3 = H*W - p1 - p2
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

    p2 = (W - w) * (H // 2)
    p3 = H*W - p1 - p2 
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))


print(ans)

Submission status: Accepted

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

ans=9999999999999

#|-----|
#| | | |
#| | | |
#|-----|
if(w%3==0):
    ans=min(ans,0)
else:
    ans=min(ans,(((w//3)+1)*h)-((w//3)*h))


#|-----|
#|-----|
#|-----|
#|-----|
if(h%3==0):
    ans=min(ans,0)
else:
    ans=min(ans,(((h//3)+1)*w)-((h//3)*w))

#|-----| |-----|
#| |   | |   | |
#| |---| |---| |
#|-----| |-----|
if(h%2==0):
    for wi in range(1,w):
        a=(h//2)*wi
        b=(h//2)*wi
        c=h*(w-wi)
        ans=min(ans, max(a,b,c)-min(a,b,c))
else:
    for wi in range(1,w):
        a=(h//2)*wi
        b=((h//2)+1)*wi
        c=h*(w-wi)
        ans=min(ans, max(a,b,c)-min(a,b,c))


#|-----| |-----|
#|  |  | |-----|
#|-----| |  |  |
#|-----| |-----|
if(w%2==0):
    for hi in range(1,h):
        a=(w//2)*hi
        b=(w//2)*hi
        c=w*(h-hi)
        ans=min(ans, max(a,b,c)-min(a,b,c))
else:
    for hi in range(1,h):
        a=(w//2)*hi
        b=((w//2)+1)*hi
        c=w*(h-hi)
        ans=min(ans, max(a,b,c)-min(a,b,c))

print(ans)