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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
if H%3==0 or W%3==0:
    answer = 0
else:
    answer = min(H, W)
# さらに小さくするには縦と横で割る
def cal(H, W):
    global answer
    h = H // 3
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))
    h += 1
    area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
    answer = min(answer, max(area)-min(area))

cal(H, W)
cal(W, H)
print(answer)
# 13

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
if H%3==0 or W%3==0:
    answer = 0
else:
    answer = min(H, W)
# さらに小さくするには縦と横で割る
h = H // 3
area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
answer = min(answer, max(area)-min(area))
h += 1
area = [h * W, (H-h) * (W//2), (H-h) * ((W+1)//2)]
answer = min(answer, max(area)-min(area))
w = W // 3
area = [w * H, (W-w) * (H//2), (W-w) * ((H+1)//2)]
answer = min(answer, max(area)-min(area))
w += 1
area = [w * H, (W-w) * (H//2), (W-w) * ((H+1)//2)]
answer = min(answer, max(area)-min(area))
print(answer)

# 13

Submission status: Accepted

Solution code:
def div(h, w):
  rep = float("inf")
  for i in range(1, h):
    a = i*w
    d = (h-i)//2
    b = d*w
    c = (h-i-d)*w
    rep = min(rep, max(a, b, c) - min(a, b, c))
    d = w//2
    b = (h-i)*d
    c = (h-i)*(w-d)
    rep = min(rep, max(a, b, c) - min(a, b, c))
  return rep

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

Submission status: Accepted

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

def div45(a,b): return int(a/b+0.5)

#縦→縦
ans1_min=H*min(div45(W,3), div45(W-div45(W,3),2), W-div45(W,3)-div45(W-div45(W,3),2))
ans1_max=H*max(div45(W,3), div45(W-div45(W,3),2), W-div45(W,3)-div45(W-div45(W,3),2))
ans1=ans1_max-ans1_min

#横→横
ans2_min=W*min(div45(H,3), div45(H-div45(H,3),2), H-div45(H,3)-div45(H-div45(H,3),2))
ans2_max=W*max(div45(H,3), div45(H-div45(H,3),2), H-div45(H,3)-div45(H-div45(H,3),2))
ans2=ans2_max-ans2_min

#縦→横
ans3_min=min(H*div45(W,3),(W-div45(W,3))*min(div45(H,2),H-div45(H,2)))
ans3_max=max(H*div45(W,3),(W-div45(W,3))*max(div45(H,2),H-div45(H,2)))
ans3=ans3_max-ans3_min

#横→縦
ans4_min=min(W*div45(H,3),(H-div45(H,3))*min(div45(W,2),W-div45(W,2)))
ans4_max=max(W*div45(H,3),(H-div45(H,3))*max(div45(W,2),W-div45(W,2)))
ans4=ans4_max-ans4_min

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

Submission status: Accepted

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

for i in range(1,H+1):
  A = i * W
  B1 = (H-i)//2 * W
  C1 = (H-i-(H-i)//2) * W
  M = max(A,B1,C1) - min(A,B1,C1)
  Mini = min(Mini,M)
  
  B2 = W//2 * (H-i)
  C2 = (W - W//2) * (H-i)
  M = max(A,B2,C2) - min(A,B2,C2)
  Mini = min(Mini,M)
  
for i in range(1,W+1):
  A = i * H
  B1 = (W-i)//2 * H
  C1 = (W-i-(W-i)//2) * H
  M = max(A,B1,C1) - min(A,B1,C1)
  Mini = min(Mini,M)
  
  B2 = H//2 * (W-i)
  C2 = (H - H//2) * (W-i)
  M = max(A,B2,C2) - min(A,B2,C2)
  Mini = min(Mini,M)
  
print(Mini)

Submission status: Accepted

Solution code:
W,H = map(int,input().split())
ans = 10**30
for i in range(1,W):
    a = H*i
    w = W - i
    b = max((w//2)*H,w*(H//2))
    c = w*H - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
for i in range(1,H):
    a = W*i
    h = H - i
    b = max((W//2)*h,W*(h//2))
    c = h*W - b
    x = max(a,b,c) - min(a,b,c)
    ans = min(ans,x)
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

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

    a=i*w
    b=(h-i)//2*w
    c=-(-(h-i)//2)*w
    ans=min(ans,max([a,b,c])-min([a,b,c]))

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

    a=i*h
    b=(w-i)//2*h
    c=-(-(w-i)//2)*h
    ans=min(ans,max([a,b,c])-min([a,b,c]))

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
  print(0)
else:
  if H % 3 == 1:
    x = (H-1)//3
    S2 = (H-x)*((W+1)//2)
  else:
    x = (H+1)//3
    S2 = (H-x)*(W//2)
  S1 = x*W
  if W % 3 == 1:
    x = (W-1)//3
    S4 = (W-x)*((H+1)//2)
  else:
    x = (W+1)//3
    S4 = (W-x)*(H//2)
  S3 = x*H
  print(min(H, W, abs(S1-S2), abs(S3-S4)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
res = float("inf")

if H * W % 3:
  for x in range(1, H):
    a = x * W
    b = (H - x) * (W // 2)
    c = (H - x) * W - b
    t = max(a, b, c) - min(a, b, c)
    res = min(res, t)
    #print(a,b,c)
  for x in range(1, W):
    a = x * H
    b = (W - x) * (H // 2)
    c = (W - x) * H - b
    t = max(a, b, c) - min(a, b, c)
    res = min(res, t)
    #print(a,b,c)
  for x in range(1, H):
    a = x * W
    b = W * ((H - x) // 2)
    c = (H - x) * W - b
    t = max(a, b, c) - min(a, b, c)
    res = min(res, t)
    #print(a,b,c)
  for x in range(1, W):
    a = x * H
    b = H * ((W - x) // 2)
    c = (W - x) * H - b
    t = max(a, b, c) - min(a, b, c)
    res = min(res, t)
  print(res)
else:
  print(0)

Submission status: Accepted

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


def hhcut(H, W):
    ans = 10**10
    for i in range(1, H-1):
        S1 = i*W

        h = H-i  # 残りの高さ
        if h % 2 == 0:
            S2 = S3 = h*W//2
        else:
            S2 = (h+1)//2*W
            S3 = (h-1)//2*W

        ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))
    return ans


def vhcut(H, W):
    ans = 10**10
    for i in range(1, H):
        S1 = i*W

        h = H-i  # 残りの高さ
        if W % 2 == 0:
            S2 = S3 = h*W//2
        else:
            S2 = (W+1)//2*h
            S3 = (W-1)//2*h

        ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))
    return ans


if W == 1:
    print(hhcut(H, W))
elif W == 2:
    print(min(hhcut(H, W), vhcut(W, H), vhcut(H, W)))
else:
    print(min(hhcut(H, W), hhcut(W, H), vhcut(W, H), vhcut(H, W)))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if not bool(H % 3 and W % 3):
    print(0)
    exit()
ans = float('inf')

n = H
m = H//2
l = H-m
for i in range(1, W):
    S1 = n*i
    S2 = m*(W-i)
    S3 = l*(W-i)
    ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))
n = W
m = W//2
l = W-m
for i in range(1, H):
    S1 = n*i
    S2 = m*(H-i)
    S3 = l*(H-i)
    ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))
if H > 3:
    ans = min(ans, (H//3+1)*W-H//3*W)
if W > 3:
    ans = min(ans, (W//3+1)*H-W//3*H)
print(ans)

Submission status: Accepted

Solution code:
def solve(x,y):
  ans=x*y
  for i in range(1,x):
    a=i*y
    b=max((x-i)*(y//2),((x-i)//2)*y)
    c=x*y-a-b
    ans=min(ans,max(a,b,c)-min(a,b,c))
  return ans

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    if h % 3 == 1:
        a = h//3
        b = a*2
        if w % 2 == 0:
            l1 = [(a+1)*w,b*w//2]
            l2 = [a*w,(b+1)*w//2]
            ans1 = min(max(l1)-min(l1),max(l2)-min(l2))
        else:
            c = w//2
            l1 = [(a+1)*w,b*(c+1),b*c]
            l2 = [a*w,(b+1)*(c+1),(b+1)*c]
            ans1 = min(max(l1)-min(l1),max(l2)-min(l2))
    else:
        a = h//3
        b = h//3*2
        c = w//2
        if w % 2 == 0:
            l1 = [(a+2)*w,b*c]
            l2 = [(a+1)*w,(b+1)*c]
            l3 = [a*w,(b+2)*c]
            l4 = [max(l1)-min(l1),max(l2)-min(l2),max(l3)-min(l3)]
            ans1 = min(l4)
        else:
            #print(a,b,c)
            l1 = [(a+2)*w,b*c,b*(c+1)]
            l2 = [(a+1)*w,(b+1)*c,(b+1)*(c+1)]
            l3 = [a*w,(b+2)*c,(b+2)*(c+1)]
            l4 = [max(l1)-min(l1),max(l2)-min(l2),max(l3)-min(l3)]
            ans1 = min(l4)
    ans1 = min(ans1,w)
    a = h
    h = w
    w = a
    if h % 3 == 1:
        a = h//3
        b = a*2
        if w % 2 == 0:
            l1 = [(a+1)*w,b*w//2]
            l2 = [a*w,(b+1)*w//2]
            ans2 = min(max(l1)-min(l1),max(l2)-min(l2))
        else:
            c = w//2
            l1 = [(a+1)*w,b*(c+1),b*c]
            l2 = [a*w,(b+1)*(c+1),(b+1)*c]
            ans2 = min(max(l1)-min(l1),max(l2)-min(l2))
    else:
        a = h//3
        b = a*2
        c = w//2
        if w % 2 == 0:
            l1 = [(a+2)*w,b*c]
            l2 = [(a+1)*w,(b+1)*c]
            l3 = [a*w,(b+2)*c]
            l4 = [max(l1)-min(l1),max(l2)-min(l2),max(l3)-min(l3)]
            ans2 = min(l4)
        else:
            #print(a,b,c)
            l1 = [(a+2)*w,b*c,b*(c+1)]
            l2 = [(a+1)*w,(b+1)*c,(b+1)*(c+1)]
            l3 = [a*w,(b+2)*c,(b+2)*(c+1)]
            l4 = [max(l1)-min(l1),max(l2)-min(l2),max(l3)-min(l3)]
            ans2 = min(l4)
    ans2 = min(ans2,w)
    print(min(ans1,ans2))

Submission status: Accepted

Solution code:
H,W=[int(c) for c in input().split()];
a=[H*(W//3),(H//2)*(W-W//3),(H-H//2)*(W-W//3)];
b=[W*(H//3),(W//2)*(H-H//3),(W-W//2)*(H-H//3)];
c=[W*((H+2)//3),(W//2)*(H*2//3),(W-W//2)*(H*2//3)];
d=[H*((W+2)//3),(H//2)*(W*2//3),(H-H//2)*(W*2//3)];
print(min((H%3!=0)*W,(W*3!=0)*H, max(a)-min(a),max(b)-min(b),max(c)-min(c),max(d)-min(d)));

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=10**10
for h in range(1,H):
    w=(W+1)//2
    S=[h*W,(H-h)*w,(H-h)*(W-w)]
    ans=min(ans,max(S)-min(S))
    h2=(H-h+1)//2
    S=[h*W,h2*W,(H-h-h2)*W]
    ans=min(ans,max(S)-min(S))    
for w in range(1,W):
    h=(H+1)//2
    S=[w*H,(W-w)*h,(W-w)*(H-h)]
    ans=min(ans,max(S)-min(S))
    w2=(W-w+1)//2
    S=[H*w,H*w2,H*(W-w-w2)]
    ans=min(ans,max(S)-min(S))
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def F(H,W):
    opt = H * W + 100
    for a in range(1,W):
        x = H * a
        y = (W-a) * (H//2)
        z = (W-a) * (H-H//2)
        d = max(x,y,z) - min(x,y,z)
        if opt > d:
            opt = d
    if W >= 3:
        a = W//3
        b = (W-a)//2
        c = W-a-b
        d = (max(a,b,c) - min(a,b,c)) * H
        if opt > d:
            opt = d
    return opt

answer = min(F(H,W),F(W,H))
print(answer)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
def calc(x, y):
  x1 = x // 2
  x2 = x - x1
  ans = min(x % 3, 1) * y
  if x == 2:
    ans = x * y
  for i in range(y):
    s1 = (i + 1) * x
    s2 = (y - i - 1) * x1
    s3 = (y - i - 1) * x2
    s = [s1, s2, s3]
    s.sort()
    cand = s[2] - s[0]
    if cand < ans:
      ans = cand
  return ans

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def div2(h, w):
    if w % 2 and h % 2:
        if w < h: w, h = h, w
        return h * (w // 2), h * (w // 2 + 1)
    else:
        return h * w // 2, h * w // 2

def main():
    h, w = MI()
    a = []
    for w1 in range(1, w // 2 + 1):
        p1 = w1 * h
        p2, p3 = div2(h, w - w1)
        a.append(max(p1, p2, p3) - min(p1, p2, p3))
    h, w = w, h
    for w1 in range(1, w // 2 + 1):
        p1 = w1 * h
        p2, p3 = div2(h, w - w1)
        a.append(max(p1, p2, p3) - min(p1, p2, p3))
    print(min(a))

main()

Submission status: Accepted

Solution code:
import math
H,W=map(int,input().split())
if H%3==0 or W%3==0:
  print(0)
  exit(0)
S=[0]*3
s=H*W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-W/3
w0=math.ceil(s/H)
h0=math.ceil(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.ceil(s1/H)
  h10=math.ceil(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=abs(S[0]-S[2])

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.ceil(s1/h1)
  h11=math.ceil(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))


S=[0]*3
s=H*W/3
w0=math.floor(s/H)
h0=math.floor(s/W)

S[0]=w0*H
w1=W-w0
if w1%2==0 or H%2==0:
  S[1]=(H*w1)//2
  S[2]=(H*w1)//2
else:
  s1=H*w1/2
  w10=math.floor(s1/H)
  h10=math.floor(s1/w1)
  S[2]=max((w1-w10)*H,(H-h10)*w1)
ans=min(ans,abs(S[0]-S[2]))

S[0]=W*h0
h1=H-h0
if h1%2==0 or W%2==0:
  S[1]=(W*h1)//2
  S[2]=(W*h1)//2
else:
  s1=h1*W/2
  w11=math.floor(s1/h1)
  h11=math.floor(s1/W)
  S[2]=max((W-w11)*h1,(h1-h11)*W)
ans=min(ans,abs(S[0]-S[2]))

print(ans)

Submission status: Accepted

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

if H%3==0 or W%3==0:
  ans=0
else:
  ans=min(W,H)
  
for h in range(1,H):
  nans=max(abs(h*W-(H-h)*(W//2)),abs(h*W-(H-h)*(W-W//2)),abs((H-h)*(W//2)-(H-h)*(W-W//2)))
  ans=min(ans,nans)
for w in range(1,W):
  nans=max(abs(w*H-(W-w)*(H//2)),abs(w*H-(W-w)*(H-H//2)),abs((W-w)*(H//2)-(W-w)*(H-H//2)))
  ans=min(ans,nans)
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 = min(H, W)
for w1 in [W // 3, W // 3 + 1]:
    w23 = W - w1
    for h2 in [H // 2, H // 2 + 1]:
        h3 = H - h2

        S1 = w1 * H
        S2 = h2 * w23
        S3 = h3 * w23

        ans = min(ans, max(S1, S2, S3) - min(S1, S2, S3))

for h1 in [H // 3, H // 3 + 1]:
    h23 = H - h1
    for w2 in [W // 2, W // 2 + 1]:
        w3 = W - w2

        S1 = h1 * W
        S2 = w2 * h23
        S3 = w3 * h23

        ans = min(ans, max(S1, S2, S3) - min(S1, S2, S3))

print(ans)

Submission status: Accepted

Solution code:
def solve(h, w):
  ans = 10**10
  for h1 in range(1, h):
    h2 = (h-h1)//2
    h3 = h-h1-h2
    M = w*max(h1, h2, h3)
    m = w*min(h1, h2, h3)
    if M-m < ans:
      ans = M-m
    h2 = h-h1
    w1 = w//2
    w2 = w-w1
    M = max(h1*w, h2*w1, h2*w2)
    m = min(h1*w, h2*w1, h2*w2)
    if M-m < ans:
      ans = M-m
  return ans
H, W = map(int, input().split())
print(min(solve(H, W), solve(W, H)))

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    ans=min(h,w)
    if h%3==0 or w%3==0:
        print(0)
        return
    for i in range(h+1):
        s1=i*w
        s2=(w//2)*(h-i)
        s3=(w-(w//2))*(h-i)
        ans=min(ans,max(s1,s2,s3)-min(s1,s2,s3))
    for i in range(w+1):
        s1=i*h
        s2=(h//2)*(w-i)
        s3=(h-(h//2))*(w-i)
        ans=min(ans,max(s1,s2,s3)-min(s1,s2,s3))
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
H, W = [int(x) for x in stdin.readline().rstrip().split()]
sa = 0
sb = 0
sc = 0
ans = 10**9

for h in range(1, H):
    sa = h*W
    sb = (H-h)*(W//2)
    sc = (H-h)*(W-(W//2))
    tmp = max(sa, sb, sc)-min(sa, sb, sc)
    ans = min(ans, tmp)

for w in range(1, W):
    sa = H*w
    sb = (W-w)*(H//2)
    sc = (W-w)*(H-(H//2))
    tmp = max(sa, sb, sc)-min(sa, sb, sc)
    ans = min(ans, tmp)

for h in range(1, H):
    sa = h*W
    sb = ((H-h)//2)*W
    sc = ((H-h)-((H-h)//2))*W
    tmp = max(sa, sb, sc)-min(sa, sb, sc)
    ans = min(ans, tmp)

for w in range(1, W):
    sa = H*w
    sb = ((W-w)//2)*H
    sc = ((W-w)-((W-w)//2))*H
    tmp = max(sa, sb, sc)-min(sa, sb, sc)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = float("inf")
for h in range(1,H):
    S1 = h*W
    S2,S3 = (H-h)*(W//2),(H-h)*(W//2+1)
    S = max(S1,S2,S3) - min(S1,S2,S3) if W%2==1 else max(S1,S2) - min(S1,S2)
    ans = min(ans,S)
    h1 = H-h
    S2,S3 = (h1//2)*W,(h1//2+1)*W
    S = max(S1,S2,S3) - min(S1,S2,S3) if h1%2==1 else max(S1,S2) - min(S1,S2)
    ans = min(ans,S)
for w in range(1,W):
    S1 = H*w
    S2,S3 = (H//2)*(W-w),(H//2+1)*(W-w)
    S = max(S1,S2,S3) - min(S1,S2,S3) if H%2==1 else max(S1,S2) - min(S1,S2)
    ans = min(ans,S)
    w1 = W-w
    S2,S3 = H*(w1//2),H*(w1//2+1)
    S = max(S1,S2,S3) - min(S1,S2,S3) if w1%2==1 else max(S1,S2) - min(S1,S2)
    ans = min(ans,S)

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    sq = 0
else:
    sq = min((H // 3 + 1 - H // 3) * W, (W // 3 + 1 - W // 3) * H)
for H, W in [[H, W], [W, H]]:
    for h in range(1, H + 1):
        sq21 = h * W
        sq22 = (H - h) * -(-W // 2)
        sq23 = (H - h) * (W // 2)
        sq = min(sq, max(sq21, sq22, sq23) - min(sq21, sq22, sq23))
print(sq)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
# p1
if H % 3 == 0 or W % 3 == 0:
    sq1 = 0
else:
    sq1 = min((H // 3 + 1 - H // 3) * W, (W // 3 + 1 - W // 3) * H)
# p2
sq2 = 10 ** 12
for h in range(1, H + 1):
    sq21 = h * W
    sq22 = (H - h) * -(-W // 2)
    sq23 = (H - h) * (W // 2)
    sq2 = min(sq2, max(sq21, sq22, sq23) - min(sq21, sq22, sq23))
# p3
sq3 = 10 ** 12
for w in range(1, W + 1):
    sq31 = w * H
    sq32 = (W - w) * -(-H // 2)
    sq33 = (W - w) * (H // 2)
    sq3 = min(sq3, max(sq31, sq32, sq33) - min(sq31, sq32, sq33))
ans = min(sq1, sq2, sq3)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

import math
#import numpy as np
#import operator
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	H,W=map(int,input().split())
	ans=[]
	target=H*W/3
	
	if (H%3)*(W%3)==0:
		ans.append(0)
	else:
		ans.append(H)
		ans.append(W)
		
		a1=math.floor(H/3)*W
		a2=(W//2)*(H-math.floor(H/3))
		a3=H*W-a1-a2
		ans.append(max(a1,a2,a3)-min(a1,a2,a3))
		
		a1=math.ceil(H/3)*W
		a2=(W//2)*(H-math.ceil(H/3))
		a3=H*W-a1-a2
		ans.append(max(a1,a2,a3)-min(a1,a2,a3))
		
		H,W=W,H
		
		a1 = math.floor(H / 3) * W
		a2 = (W // 2) * (H - math.floor(H / 3))
		a3 = H * W - a1 - a2
		ans.append(max(a1, a2, a3) - min(a1, a2, a3))
		
		a1 = math.ceil(H / 3) * W
		a2 = (W // 2) * (H - math.ceil(H / 3))
		a3 = H * W - a1 - a2
		ans.append(max(a1, a2, a3) - min(a1, a2, a3))
		
	print(min(ans))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    S = H * W
    ans = float('inf')
    for h1 in range(1,H):
        S1 = h1 * W
        # 縦に分割する場合
        h2 = (H - h1) // 2
        S2 = h2 * W
        S3 = (H - h1 - h2) * W
        ans = min(ans, max(S1,S2,S3) - min(S1,S2,S3))
        # 横に分割する場合
        w2 = W // 2
        w3 = W - w2
        S2 = (H - h1) * w2
        S3 = (H - h1) * w3
        ans = min(ans, max(S1,S2,S3) - min(S1,S2,S3))

    for w1 in range(1,W):
        S1 = w1 * H
        # 横に分割する場合
        w2 = (W - w1) // 2
        S2 = w2 * H
        S3 = (W - w1 - w2) * H
        ans = min(ans, max(S1,S2,S3) - min(S1,S2,S3))
        # 縦に分割する場合
        h2 = H // 2
        h3 = H - h2
        S2 = (W - w1) * h2
        S3 = (W - w1) * h3
        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())
if not h % 3 or not w % 3:
    print(0)
    exit()
    
ans = min(h, w)
for i in range(1, h):
    a = i * w
    b = (h - i) * (w // 2)
    c = h * w - (a + b)
    ans = min(ans, abs(max(a, b, c) - min(a, b, c)))

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

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
ans = float("inf")
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    for i in range(1, W):
        a = H * i
        b = (W - i) * (H // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
        # 縦割り
        a = H * i
        b = H * ((W - i) // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
    for i in range(1, H):
        a = W * i
        b = (H - i) * (W // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)
        # 縦割り
        a = W * i
        b = W * ((H - i) // 2)
        c = H * W - a - b
        S_min = min(a, min(b, c))
        S_max = max(a, max(b, c))
        ans = min(ans, S_max - S_min)

print(ans)

Submission status: Accepted

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

def calc(a,b):
  res = 10**9
  for i in range(1,a-1):
    S1 = i*b
    S2 = (a-i)//2*b
    S3 = ((a-i)-((a-i)//2))*b
    res = min(res,max(S1,S2,S3)-min(S1,S2,S3))
  for i in range(1,a):
    S1 = i*b
    S2 = (a-i)*(b//2)
    S3 = (a-i)*(b-(b//2))
    res = min(res,max(S1,S2,S3)-min(S1,S2,S3))
  return res

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = float("inf")
if H%3!=0:
    ans = W
else:
    ans = 0
if W%3!=0:
    ans = min(ans, H)
else:
    ans = min(ans,0)
#print(ans)
for i in range(1,W):
    Sma = max(i*H, (W-i)*(-(-H//2)))
    Smi = min(i*H, (W-i)*(H//2))
    ans = min(ans, Sma-Smi)

for i in range(1,H):
    Sma = max(i*W, (H-i)*(-(-W//2)))
    Smi = min(i*W, (H-i)*(W//2))
    ans = min(ans, Sma-Smi)
print(ans)

Submission status: Accepted

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

a = 0
b = 0
c = 0
ans = 1e+9

for ha in range(1, max(2, h-1)):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha) * (w//2)
    c = (h-ha) * math.ceil(w/2)
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

for ha in range(1, max(2, h-1)):  # bとcを縦に分割するパターン
    a = ha * w
    b = (h-ha)//2 * w
    c = math.ceil((h-ha)/2) * w
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

h, w = w, h

for ha in range(1, max(2, h-1)):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha) * (w//2)
    c = (h-ha) * math.ceil(w/2)
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

for ha in range(1, max(2, h-1)):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha)//2 * w
    c = math.ceil((h-ha)/2) * w
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

print(int(ans))

Submission status: Accepted

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

a = 0
b = 0
c = 0
ans = 1e+9

if h == 2 and w == 2:
    print(1)
    exit()

for ha in range(1, h-1):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha) * (w//2)
    c = (h-ha) * math.ceil(w/2)
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

for ha in range(1, h-1):  # bとcを縦に分割するパターン
    a = ha * w
    b = (h-ha)//2 * w
    c = math.ceil((h-ha)/2) * w
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

h, w = w, h

for ha in range(1, h-1):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha) * (w//2)
    c = (h-ha) * math.ceil(w/2)
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

for ha in range(1, h-1):  # bとcを横に分割するパターン
    a = ha * w
    b = (h-ha)//2 * w
    c = math.ceil((h-ha)/2) * w
    smax = max(a, max(b, c))
    smin = min(a, min(b, c))
    ans = min(ans, smax-smin)

print(int(ans))

Submission status: Accepted

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

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

ans=10**10
for i in range(1,H):
  ans=min(ans,d(i*W,((H-i)//2)*W,(H-i-(H-i)//2)*W))
for i in range(1,H):
  ans=min(ans,d(i*W,(H-i)*(W//2),(H-i)*(W-W//2)))

H,W=W,H
for i in range(1,H):
  ans=min(ans,d(i*W,((H-i)//2)*W,(H-i-(H-i)//2)*W))
for i in range(1,H):
  ans=min(ans,d(i*W,(H-i)*(W//2),(H-i)*(W-W//2)))

print(ans)

Submission status: Accepted

Solution code:
def main():
    from math import floor, ceil
    h, w = map(int, input().split(' '))
    result = []
    if h%3 == 0 or w%3 == 0:
        print(0)
    elif h<3 or w<3:
        if h<3 and w>=3:
            for i in range(1, w-1):
                x = i*h
                y = (w-i)*floor(h/2)
                z = (w-i)*ceil(h/2)
                result.append(max(x,y,z)-min(x,y,z))
                y = floor((w-i)/2)*h
                z = ceil((w-i)/2)*h
                result.append(max(x,y,z)-min(x,y,z))
            print(min(result))
        elif h>=3 and w<3:
            for i in range(1, h-1):
                x = i*w
                y = (h-i)*floor(w/2)
                z = (h-i)*ceil(w/2)
                result.append(max(x,y,z)-min(x,y,z))
                y = floor((h-i)/2)*w
                z = ceil((h-i)/2)*w
                result.append(max(x,y,z)-min(x,y,z))
            print(min(result))
        else:
            print(1)
    else:
        for i in range(1, h-1):
            x = i*w
            y = (h-i)*floor(w/2)
            z = (h-i)*ceil(w/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((h-i)/2)*w
            z = ceil((h-i)/2)*w
            result.append(max(x,y,z)-min(x,y,z))
        for i in range(1, w-1):
            x = i*h
            y = (w-i)*floor(h/2)
            z = (w-i)*ceil(h/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((w-i)/2)*h
            z = ceil((w-i)/2)*h
            result.append(max(x,y,z)-min(x,y,z))
        print(min(result))
main()

Submission status: Accepted

Solution code:
from math import floor, ceil
h, w = map(int, input().split(' '))
result = []
if h%3 == 0 or w%3 == 0:
    print(0)
elif h<3 or w<3:
    if h<3 and w>=3:
        for i in range(1, w-1):
            x = i*h
            y = (w-i)*floor(h/2)
            z = (w-i)*ceil(h/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((w-i)/2)*h
            z = ceil((w-i)/2)*h
            result.append(max(x,y,z)-min(x,y,z))
        print(min(result))
    elif h>=3 and w<3:
        for i in range(1, h-1):
            x = i*w
            y = (h-i)*floor(w/2)
            z = (h-i)*ceil(w/2)
            result.append(max(x,y,z)-min(x,y,z))
            y = floor((h-i)/2)*w
            z = ceil((h-i)/2)*w
            result.append(max(x,y,z)-min(x,y,z))
        print(min(result))
    else:
        print(1)
else:
    for i in range(1, h-1):
        x = i*w
        y = (h-i)*floor(w/2)
        z = (h-i)*ceil(w/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((h-i)/2)*w
        z = ceil((h-i)/2)*w
        result.append(max(x,y,z)-min(x,y,z))
    for i in range(1, w-1):
        x = i*h
        y = (w-i)*floor(h/2)
        z = (w-i)*ceil(h/2)
        result.append(max(x,y,z)-min(x,y,z))
        y = floor((w-i)/2)*h
        z = ceil((w-i)/2)*h
        result.append(max(x,y,z)-min(x,y,z))
    print(min(result))

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    H,W = map(int, input().split())
    if H%3 == 0 or W%3 == 0:
        print(0)
    else:
        mi = H*W
        # 縦3分割パターン
        s = W*math.ceil(H/3) - W*math.floor(H/3)
        mi = min(mi, s)
        # 横3分割パターン
        s = H*math.ceil(W/3) - H*math.floor(W/3)
        mi = min(mi, s)
        # 下2分割パターン
        for h in range(1,H):
            a = h*W
            b = (H-h)*math.ceil(W/2)
            c = (H-h)*math.floor(W/2)
            mi = min(mi, max(a,b,c) - min(a,b,c))
        # 右2分割パターン
        for w in range(1,W):
            a = H*w
            b = math.ceil(H/2)*(W-w)
            c = math.floor(H/2)*(W-w)
            mi = min(mi, max(a,b,c) - min(a,b,c))
        print(mi)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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

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

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