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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    
    ans = 10 ** 10
    for y1 in range(1, H):
        s1 = y1 * W
        y2 = (H - y1) // 2
        y3 = H - y1 - y2
        s2 = y2 * W
        s3 = y3 * W
        ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
        x2 = W // 2
        x3 = W - x2
        s2 = (H - y1) * x2
        s3 = (H - y1) * x3
        ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    
    for x1 in range(1, W):
        s1 = x1 * H
        x2 = (W - x1) // 2
        x3 = W - x1 - x2
        s2 = x2 * H
        s3 = x3 * H
        ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
        y2 = H // 2
        y3 = H - y2
        s2 = (W - x1) * y2
        s3 = (W - x1) * y3
        ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()

    ans = INF
    for i in range(1,H):
        b1 = i * W
        b2 = (H-i) * (W//2)
        b3 = (H-i) * (W - W//2)
        ans = min(ans,max(b1,b2,b3) - min(b1,b2,b3))
        b2 = ((H-i)//2) * W
        b3 = ((H-i) - (H-i)//2) * W
        ans = min(ans,max(b1,b2,b3) - min(b1,b2,b3))
        
    for i in range(1,W):
        b1 = i * H
        b2 = (W - i) * (H // 2)
        b3 = (W - i) * (H - H // 2)
        ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))
        b2 = ((W - i) // 2) * H
        b3 = ((W - i) - (W - i) // 2) * H
        ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    H,W = LI()

    ans = INF

    for i in range(1,H):
        b1 = i * W
        b2 = (H-i) * (W//2)
        b3 = (H-i) * (W - W//2)
        ans = min(ans,max(b1,b2,b3) - min(b1,b2,b3))

        if i < H-1:
            b2 = ((H-i)//2) * W
            b3 = ((H-i) - (H-i)//2) * W
            ans = min(ans,max(b1,b2,b3) - min(b1,b2,b3))
    for i in range(1,W):
        b1 = i * H
        b2 = (W - i) * (H // 2)
        b3 = (W - i) * (H - H // 2)
        ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))

        if i < W - 1:
            b2 = ((W - i) // 2) * H
            b3 = ((W - i) - (W - i) // 2) * H
            ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc(W, H):
    ans = float("inf")
    for w in range(1, W//2+1):
        x = w * H
        w_ = W - w
        if w_ % 2 == 0 or H % 2 == 0:
            y = (w_*H)//2
            li = sorted([x, y, y])
        else:
            if w_ < H:
                a, b = w_, H
            else:
                a, b = H, w_
            y = a * (b//2)
            z = a * (b-b//2)
            li = sorted([x,y,z])
        ans = min(ans, li[2] - li[0])
    return ans



def main():
    import sys
    input = sys.stdin.readline
    w, h = map(int, input().split())
    ans = calc(w,h)
    ans = min(calc(h,w), ans)
    print(ans)


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)
else:
  h2 = [H//2,H//2+1]
  h3 = [H//3,H//3+1,H//3+2]  
  w2 = [W//2,W//2+1]
  w3 = [W//3,W//3+1,W//3+2]
  ans = float("inf")
  #最初に縦切り
  for i in range(3):
    for j in range(2):
      a = H*w3[i]
      b = (W-w3[i])*h2[j]
      c = H*W - a - b 
      ans = min(ans , max(a,b,c) - min(a,b,c) )    
  #横  
  for i in range(3):
    for j in range(2):
      a = W*h3[i]
      b = (H-h3[i])*w2[j]
      c = H*W - a - b 
      ans = min(ans , max(a,b,c) - min(a,b,c) ) 
  #縦横の完全三等分パターン
  for i in range(3):
    for j in range(2):
      a = h3[i]
      b = (H-h3[i])//2
      c = H-a-b
      ans = min(ans , W*(max(a,b,c) - min(a,b,c)) )
      a = w3[i]
      b = (W-w3[i])//2
      c = W-a-b
      ans = min(ans , H*(max(a,b,c) - min(a,b,c)) )    
  print(ans)

Submission status: Accepted

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

from fractions import gcd
def resolve():
    H,W=pin()
    #たてに切る
    hori=0 if W%3==0 else H
    #よこにきる
    vert=0 if H%3==0 else W
    #たてに切った後よこ
    sp1=H*W
    for w in range(W):
        g=H*(w+1)
        #b>=rとする
        t=(H+1)//2
        b=t*(W-w-1)
        r=(H//2)*(W-w-1)
        sp1=min(sp1,max(g,b,r)-min(g,b,r))
    #横に切った後たて
    sp2=H*W
    for h in range(H):
        g=W*(h+1)
        #b>=rとする
        t=(W+1)//2
        b=t*(H-h-1)
        r=(W//2)*(H-h-1)
        sp2=min(sp2,max(g,b,r)-min(g,b,r))
    #上4つの最小 間に合ってほしいねぇ
    print(min(hori,vert,sp1,sp2))
#%%submit!
resolve()

Submission status: Accepted

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

def calc(n):
    if n%3==0:
        return True
    else:
        return False

if calc(H) or calc(W):
    print(0)
    exit()

ans=10**10
for h in range(1,H+1):
    Sa=h*W
    h_=(H-h)//2
    Sb=h_*W
    Sc=(H-h-h_)*W
    SM=max(Sa,Sb,Sc)
    Sm=min(Sa,Sb,Sc)
    ans=min(SM-Sm,ans)
    w=W//2
    Sb=(H-h)*w
    Sc=(H-h)*(W-w)
    SM=max(Sa,Sb,Sc)
    Sm=min(Sa,Sb,Sc)
    ans=min(SM-Sm,ans)

tmp=H
H=W
W=tmp
for h in range(1,H+1):
    Sa=h*W
    h_=(H-h)//2
    Sb=h_*W
    Sc=(H-h-h_)*W
    SM=max(Sa,Sb,Sc)
    Sm=min(Sa,Sb,Sc)
    ans=min(SM-Sm,ans)
    w=W//2
    Sb=(H-h)*w
    Sc=(H-h)*(W-w)
    SM=max(Sa,Sb,Sc)
    Sm=min(Sa,Sb,Sc)
    ans=min(SM-Sm,ans)
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split(" "))
ans = 10 ** 10
karians = [0,0,0]
if H % 3 == 0 or W % 3 == 0:
    ans = 0
k = int(W / 2)
for i in range(H + 1):
    karians = [i * W,k * (H - i),(W - k) * (H - i)]
    karians.sort()
    if (karians[2] - karians[0] < ans):
        ans = karians[2] - karians[0]
k = int(H / 2)
for i in range(W + 1):
    karians = [i * H,k * (W - i),(H - k) * (W - i)]
    karians.sort()
    if (karians[2] - karians[0] < ans):
        ans = karians[2] - karians[0]
if(W < ans): ans = W
if(H < ans): ans = H

print(ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return
    if H % 2 == 0 or W % 2 == 0:
        if W % 2 != 0:
            print(min(H // 2, W))
            return
        if H % 2 != 0:
            print(min(W // 2, H))
            return
        else:
            if H >= W:
                print(W // 2)
                return
            else:
                print(H // 2)
                return

    if H == 1:
        print(1)
        return
    if W == 1:
        print(1)
        return
    else:
        answer = float("inf")
        for i in range(1, H):
            m = W // 2
            choco = [i * W, m * (H - i), (m + 1) * (H - i)]
            ans = max(choco) - min(choco)
            if answer > ans:
                answer = ans

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    ans = INF
    for i in range(2):
        if i == 1:
            H, W = W, H

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

            if (H - h) % 2 == 0:
                a2 = (H - h) // 2 * W
                tmp = abs(a1 - a2)
                if tmp < ans:
                    ans = tmp
            else:
                h2 = (H - h) // 2
                a2 = h2 * W
                a3 = (h2 + 1) * W
                tmp = abs(a2 - a3)
                if tmp < ans:
                    ans = tmp

            if W % 2 == 0:
                a2 = (H - h) * (W // 2)
                tmp = abs(a1 - a2)
                if tmp < ans:
                    ans = tmp
            else:
                w = W // 2
                a2 = (w + 1) * (H - h)
                a3 = w * (H - h)
                M = max(a1, a2, a3)
                m = min(a1, a2, a3)
                tmp = abs(M - m)
                if tmp < ans:
                    ans = tmp

    print(ans)


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

ans = H * W
s = [0] * 3

for i in range(2):
	for h in range(1, H):
		# 縦割り
		s[0] = h * W
		s[1] = (H - h) * (W // 2)
		s[2] = H * W - (s[0] + s[1])
		s.sort()
		ans = min(ans, s[2] - s[0])

		# 横割り
		s[0] = h * W
		s[1] = ((H - h) // 2) * W
		s[2] = H * W - (s[0] + s[1])
		s.sort()
		ans = min(ans, s[2] - s[0])

	# 縦と横の入れ替え
	H, W = W, H

print(ans)

Submission status: Accepted

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

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

for i in range(1,W//2 + 1):
    l = (W - i) // 2
    r = W - i - l
    ans = min(ans, max(H*i, H*l, H*r) - min(H*i, H*l, H*r), max(H*i, h*(W-i), (H-h)*(W-i)) - min(H*i, h*(W-i), (H-h)*(W-i)))

print(ans)

Submission status: Accepted

Solution code:
h, w = [int(x) for x in input().split()]
d1 = min(max(w1 * h, (w - w1) * (h // 2), (w - w1) * ((h + 1) // 2))
       - min(w1 * h, (w - w1) * (h // 2), (w - w1) * ((h + 1) // 2)) for w1 in range(1, w))
d2 = min(max(w1 * h, ((w - w1) // 2) * h, ((w - w1 + 1) // 2) * h) 
       - min(w1 * h, ((w - w1) // 2) * h, ((w - w1 + 1) // 2) * h) for w1 in range(1, w))
d3 = min(max(h1 * w, (h - h1) * (w // 2), (h - h1) * ((w + 1) // 2)) 
       - min(h1 * w, (h - h1) * (w // 2), (h - h1) * ((w + 1) // 2)) for h1 in range(1, h))
d4 = min(max(h1 * w, ((h - h1) // 2) * w, ((h - h1 + 1) // 2) * w) 
       - min(h1 * w, ((h - h1) // 2) * w, ((h - h1 + 1) // 2) * w) for h1 in range(1, h))
print(min(d1, d2, d3, d4))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
if h%3==0 or w%3==0:
    print(0)
    exit()
# both vert or both horiz
mn = min(h,w)

# h/3, then v
hh = h//3
s1 = hh*w # < S/3
ww = w//2 + w%2
s2 = (h-hh)*ww # > S/3
mn = min(mn, s2-s1)
#ddprint(f"1. hh {hh} ww {ww} dif {s2-s1}")

# h/3+1, then v
hh = h//3+1
s1 = hh*w # > S/3
ww = w//2
s2 = (h-hh)*ww # < S/3
mn = min(mn, s1-s2)
#ddprint(f"2. hh {hh} ww {ww} dif {s1-s2}")

# w/3, then h
ww = w//3
s1 = ww*h # < S/3
hh = h//2 + h%2
s2 = (w-ww)*hh # > S/3
mn = min(mn, s2-s1)
#ddprint(f"3. hh {hh} ww {ww} dif {s2-s1}")

# w/3+1, then h
ww = w//3+1
s1 = ww*h # > S/3
hh = h//2
s2 = (w-ww)*hh # < S/3
mn = min(mn, s1-s2)
#ddprint(f"4. hh {hh} ww {ww} dif {s1-s2}")

print(mn)

Submission status: Accepted

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

# ちょうど3等分できるなら、0
if H%3==0 or W%3==0:
    print(0)
    quit()

mind = 10**18

for h in range(H+1):
    a = [W*h]
    if W%2==0 or (H-h)%2==0:
        a.append(int(W/2*(H-h)))
    else:
        a.append(W*(H-h)-min(H-h, W)*(max(H-h, W)//2))
        a.append(W*(H-h)-a[-1])
    mind = min(mind, max(a)-min(a))


for w in range(W+1):
    a = [w*H]
    if (W-w)%2==0 or H%2==0:
        a.append(int((W-w)/2*H))
    else:
        a.append((W-w)*H-min(W-w, H)*(max(W-w, h)//2))
        a.append((W-w)*h-a[-1])
    mind = min(mind, max(a)-min(a))

print(mind)

Submission status: Accepted

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

ans = float('inf')
a,b,c = H//3*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (H+2)//3*W,(H-(H+2)//3)*(W//2),(H-(H+2)//3)*(W-W//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = (W+2)//3*H,(W-(W+2)//3)*(H//2),(W-(W+2)//3)*(H-H//2)
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = H//3*W,H//3*W,((H+2)//3)*W
ans = min(ans,max(a,b,c)-min(a,b,c))
a,b,c = W//3*H,W//3*H,((W+2)//3)*H
ans = min(ans,max(a,b,c)-min(a,b,c))

print(ans)

Submission status: Accepted

Solution code:
H,W = list(map(int,input().split()))
if H%3 == 0 or W%3 == 0:
    print(0)
else:
    ans = float('inf')
    a,b,c = H//3*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)
    ans = min(ans,max(a,b,c)-min(a,b,c))
    a,b,c = (H+2)//3*W,(H-(H+2)//3)*(W//2),(H-(H+2)//3)*(W-W//2)
    ans = min(ans,max(a,b,c)-min(a,b,c))
    a,b,c = W//3*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)
    ans = min(ans,max(a,b,c)-min(a,b,c))
    a,b,c = (W+2)//3*H,(W-(W+2)//3)*(H//2),(W-(W+2)//3)*(H-H//2)
    ans = min(ans,max(a,b,c)-min(a,b,c))
    a,b,c = H//3*W,H//3*W,(H//3+1)*W
    ans = min(ans,max(a,b,c)-min(a,b,c))
    a,b,c = W//3*H,W//3*H,(W//3+1)*H
    ans = min(ans,max(a,b,c)-min(a,b,c))

    print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc026/tasks/arc026_2
import math,itertools,fractions,heapq,collections,bisect,sys,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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

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

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

    a=i*h
    b=(w-i)*((h+1)//2)
    c=(w-i)*(h//2)
    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())
S = H * W
ans = float('inf')
for h in range(1, H):
    Sa = h * W
    Sb = (H - h) // 2 * W
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (H - h) * (W // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
for w in range(1, W):
    Sa = H * w
    Sb = (W - w) // 2 * H
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (W - w) * (H // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = H * W
ans = float('inf')
for h in range(1, H):
    Sa = h * W
    Sb = (H - h) // 2 * W
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (H - h) * (W // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
for w in range(1, W):
    Sa = H * w
    Sb = (W - w) // 2 * H
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (W - w) * (H // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
print(ans)

Submission status: Accepted

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

def area(h,w,p):
    if p==1:
        return h*w,h*w
    cmin=10**10+1
    hh=h//p
    if hh>0:
        sh=hh*w
        smax,smin=area(h-hh,w,p-1)

        tmax=max(sh,smax)
        tmin=min(sh,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    hh+=1
    if hh<h:
        sh=hh*w
        smax,smin=area(h-hh,w,p-1)

        tmax=max(sh,smax)
        tmin=min(sh,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    ww=w//p
    if ww>0:
        sw=ww*h
        smax,smin=area(h,w-ww,p-1)

        tmax=max(sw,smax)
        tmin=min(sw,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    ww+=1
    if ww<w:
        sw=ww*h
        smax,smin=area(h,w-ww,p-1)

        tmax=max(sw,smax)
        tmin=min(sw,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin
    
    return retmax,retmin

smax,smin=area(h,w,3)
print(smax-smin)

Submission status: Accepted

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

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

        b = (H-i)*(W//2)
        c = (H-i)*((W + 1)//2)
        ans = min(ans, abs(max(a, b, c) - min(a, b, c)))
    H, W = W, H
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( ))
#縦3
ans1 = h*((w+2)//3-(w//3))
#横3
ans2 = w*((h+2)//3-(h//3))

#T型
mn = min((h//3)*w, (h-h//3)*(w//2), (h-h//3)*((w+1)//2))
mx = max((h//3)*w, (h-h//3)*(w//2), (h-h//3)*((w+1)//2))
ans3 = mx-mn

#T型
mn = min(((h+2)//3)*w, (h-(h+2)//3)*(w//2), (h-(h+2)//3)*((w+1)//2))
mx = max(((h+2)//3)*w, (h-(h+2)//3)*(w//2), (h-(h+2)//3)*((w+1)//2))
ans4 = mx-mn

#横T
h,w=w,h
mn = min((h//3)*w, (h-h//3)*(w//2), (h-h//3)*((w+1)//2))
mx = max((h//3)*w, (h-h//3)*(w//2), (h-h//3)*((w+1)//2))
ans5 = mx-mn
mn = min(((h+2)//3)*w, (h-(h+2)//3)*(w//2), (h-(h+2)//3)*((w+1)//2))
mx = max(((h+2)//3)*w, (h-(h+2)//3)*(w//2), (h-(h+2)//3)*((w+1)//2))
ans6 = mx-mn



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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**6
for i in range(1,h):
    A=i*w
    bh=int((h-i)/2)
    B1=bh*w
    C1=(h-i-bh)*w
    tmp1=max(A,B1,C1)-min(A,B1,C1)
    bw=int(w/2)
    B2=(h-i)*bw
    C2=(h-i)*(w-bw)
    tmp2=max(A,B2,C2)-min(A,B2,C2)
    ans=min(ans,tmp1,tmp2)
x=w
w=h
h=x
ans2=10**6
for i in range(1,h):
    A=i*w
    bh=int((h-i)/2)
    B1=bh*w
    C1=(h-i-bh)*w
    tmp1=max(A,B1,C1)-min(A,B1,C1)
    #print("Aの高さ={}, Bの高さ={}, Bの横幅={}, Cの高さ={}, Cの横幅={}, A={} B={} C={} tmp={}".format(i,bh,w,h-i-bh,w,A,B1,C1,tmp1))
    bw=int(w/2)
    B2=(h-i)*bw
    C2=(h-i)*(w-bw)
    tmp2=max(A,B2,C2)-min(A,B2,C2)
    #print("Aの高さ={}, Bの高さ={}, Bの横幅={}, Cの高さ={}, Cの横幅={}, A={} B={} C={} tmp2={}".format(i,h-i,bw,h-i,w-bw,A,B2,C2,tmp2))
    ans2=min(ans2,tmp1,tmp2)
print(min(ans,ans2))

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    ans = 10**10
    # 縦or横に三分割
    if W % 3 == 0 or H % 3 == 0:
        ans = 0
        return print(ans)
    else:
        ans = min(H, W)

    # 分割の位置を探索
    for w in range(1, W):
        a = H*w
        b = (H//2)*(W-w)
        c = (H-(H//2))*(W-w)
        ans = min(ans, max(a, b, c) - min(a, b, c))
    for h in range(1, H):
        a = h*W
        b = (H-h)*(W//2)
        c = (H-h)*(W-(W//2))
        ans = min(ans, max(a, b, c) - min(a, b, c))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
mnr = 10**18
for i in range(1, H):
    w1 = W//2
    w2 = W-w1
    s1, s2, s3 = i*W, w1*(H-i), w2*(H-i)
    t = max([s1, s2, s3]) - min([s1, s2, s3])
    mnr = min(mnr, t)
H, W = W, H
for i in range(1, H):
    w1 = W//2
    w2 = W-w1
    s1, s2, s3 = i*W, w1*(H-i), w2*(H-i)
    t = max([s1, s2, s3]) - min([s1, s2, s3])
    mnr = min(mnr, t)
if H % 3 == 0 or W % 3== 0:
    mnr = 0
if H % 3:
    mnr = min(W, mnr)
if W % 3:
    mnr = min(H, mnr)
print(mnr)

Submission status: Accepted

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

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

#print(h, w)
min_ = float('inf')
for i in range(1, h):
    s1 = w*i
    s2 = (h-i)*(w//2)
    s3 = (h-i)*(w-w//2)
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)

    s2 = ((h-i)//2)*w
    s3 = ((h-i) - (h-i)//2)*w
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)

#print('-')

for i in range(1, w):
    s1 = h*i
    s2 = (w-i)*(h//2)
    s3 = (w-i)*(h-h//2)
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)

    s2 = ((w-i)//2)*h
    s3 = ((w-i) - (w-i)//2)*h
    d = max([s1, s2, s3]) - min([s1, s2, s3])
    #print(i, s1, s2, s3, d)
    min_ = min(min_, d)

print(min_)

Submission status: Accepted

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

ans = 10 ** 18

# 平行に三分割出来れば答えは0
Hsplit = W * ((H + 2) // 3 - H // 3)
Wsplit = H * ((W + 2) // 3 - W // 3)
ans = min(ans, Hsplit, Wsplit)

# 縦横に分割


def calc(X, Y):
    res = 10 ** 18

    Ymax = (Y + 1) // 2
    Ymin = Y // 2
    for i in range(1, X):
        s1 = Ymax * i
        s2 = Ymin * i
        s3 = Y * (X - i)
        res = min(res, max(s1, s2, s3) - min(s1, s2, s3))
    return res


ans = min(ans, calc(H, W))
ans = min(ans, calc(W, 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 = min(H,W)

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

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

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ans = h*w

for x,y in [[h,w],[w,h]]:
    for margin_x in [0,1]:
        for second_cut in ['x','y']:
            area = [0] * 3
            area[0] = (x//3 + margin_x) * y
            x2 = x - (x//3 + margin_x)
            if(second_cut == 'x'):
                area[1] = (x2//2) * y
                area[2] = (x2 - x2//2) * y
            else:
                area[1] = x2 * (y//2)
                area[2] = x2 * (y - y//2)
            ans = min(ans, max(area)-min(area))

            if(ans == 0):
                print(ans)
                exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

H,W = LI()

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

ans = min(H,W)
for i in range(H):
    num1 = W*i
    num2 = math.floor(W/2)*(H-i)
    num3 = math.ceil(W/2)*(H-i)
    now = max(num1,num2,num3)-min(num1,num2,num3)
    if now < ans:
        ans = now

for i in range(W):
    num1 = H*i
    num2 = math.floor(H/2)*(W-i)
    num3 = math.ceil(H/2)*(W-i)
    now = max(num1,num2,num3)-min(num1,num2,num3)
    if now < ans:
        ans = now

print(ans)

Submission status: Accepted

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

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

def getmin(h,w):
    min_w = 10**10

    if h%2==0:
        h1=h//2
        h2=h//2
    else:
        h1=h//2
        h2=h1+1

    for i in range(1,w):
        if (w-i)%2==0:
            w1=(w-i)//2
            w2=(w-i)//2
        else:
            w1=(w-i)//2
            w2=w1+1
        area1=h*i
        area2=h1*(w-i)
        area3=h2*(w-i)

        area2w=h*w1
        area3w=h*w2

        lis=[area1,area2,area3]
        lisw=[area1,area2w,area3w]
        lis.sort()
        lisw.sort()
        dif=10**9
        difw=10**9
        if lis[0] > 0:
            dif = lis[2] - lis[0]
        if lisw[0] > 0:
            difw = lisw[2] - lisw[0]

        if min_w > dif:
            min_w=dif
        if min_w > difw:
            min_w=difw

    return min_w

print(min(getmin(h,w),getmin(w,h)))

Submission status: Accepted

Solution code:
def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    if h == 1 or w == 1:
        return 1
    def f(a, b):
        vals = [0, 0, 0]
        min_diff = h * w
        for i in range(1, a // 2 + 1):
            vals[0] = i * b
            vals[1] = (a - i) * (b // 2 + b % 2)
            vals[2] = (a - i) * (b // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
            vals[1] = b * ((a - i) // 2 + (a - i) % 2)
            vals[2] = b * ((a - i) // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
        return min_diff
    return min(f(h, w), f(w, h))

_h, _w = map(int, input().split())
print(solve(_h, _w))

Submission status: Accepted

Solution code:
def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    if w < h:
        h, w = w, h
    if h == 1:
        return 1
    min_diff = h * w
    vals = [0, 0, 0]
    for i in range(1, w // 2 + 1):
        vals[0] = i * h
        if h % 2 == 0:
            vals[1] = (w - i) * (h // 2)
            vals[2] = vals[1]
        else:
            vals[1] = (w - i) * (h // 2 + 1)
            vals[2] = (w - i) * (h // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
        if (w - i) % 2 == 0:
            vals[1] = h * ((w - i) // 2)
            vals[2] = vals[1]
        else:
            vals[1] = h * ((w - i) // 2 + 1)
            vals[2] = h * ((w - i) // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
    h, w = w, h
    for i in range(1, w // 2 + 1):
        vals[0] = i * h
        if h % 2 == 0:
            vals[1] = (w - i) * (h // 2)
            vals[2] = vals[1]
        else:
            vals[1] = (w - i) * (h // 2 + 1)
            vals[2] = (w - i) * (h // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
        if (w - i) % 2 == 0:
            vals[1] = h * ((w - i) // 2)
            vals[2] = vals[1]
        else:
            vals[1] = h * ((w - i) // 2 + 1)
            vals[2] = h * ((w - i) // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
    return min_diff

_h, _w = map(int, input().split())
print(solve(_h, _w))

Submission status: Accepted

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

else:
    for m in range(2):
        H,W=W,H
        if H%2==0:
            A1=(H//2)* W
        else:
            A1=(H//2 +1)* W
        A2=(H//2)* W
        A3=0
        if m == 0:
            value=max(A1,A2,A3)-min(A1,A2,A3)
        else:
            value=min(max(A1,A2,A3)-min(A1,A2,A3),value)
        for i in range(W):
            A3+=H
            if H%2==0:
                A1-=H//2
            else:
                A1-=H//2 + 1
            A2-=H//2
            value=min(max(A1,A2,A3)-min(A1,A2,A3),value)
    value=min(value,H,W)



    print(value)

Submission status: Accepted

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

if h*w%3 != 0:
    def div(x,y):
        res = float("inf")
        for i in range(1,x):
            r = x-i
            d1 = (i*y,(r//2)*y,((r+1)//2)*y)
            d2 = (i*y,r*(y//2),r*((y+1)//2))
            m = min(map(lambda x:max(x)-min(x),(d1,d2)))
            res = min(res,m)
        return res
    ans = min(div(h,w),div(w,h))

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mx=10**18
for i in range(1,h):
  l=w//2
  s=[i*w,(h-i)*l,(h-i)*(w-l)]
  s.sort()
  mx=min(mx,s[2]-s[0])
  k=(h-i)//2
  t=[i*w,k*w,(h-k-i)*w]
  t.sort()
  mx=min(mx,t[2]-t[0])
for i in range(1,w):
  l=h//2
  s=[i*h,(w-i)*l,(w-i)*(h-l)]
  s.sort()
  mx=min(mx,s[2]-s[0])
  k=(w-i)//2
  t=[i*h,k*h,(w-k-i)*h]
  t.sort()
  mx=min(mx,t[2]-t[0])
print(mx)