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())
l=[]
for i in range(1,h):
  s1=w*i
  s2=(h-i)*(w//2)
  s3=h*w-s1-s2
  l.append(max(s1,s2,s3)-min(s1,s2,s3))
for i in range(1,w):
  s1=h*i
  s2=(w-i)*(h//2)
  s3=h*w-s1-s2
  l.append(max(s1,s2,s3)-min(s1,s2,s3))
for i in range(1,h-1):
  s1=w*i
  s2=w*((h-i)//2)
  s3=w*h-s1-s2
  l.append(max(s1,s2,s3)-min(s1,s2,s3))
for i in range(1,w-1):
  s1=h*i
  s2=h*((w-i)//2)
  s3=w*h-s1-s2
  l.append(max(s1,s2,s3)-min(s1,s2,s3))
print(min(l))

Submission status: Accepted

Solution code:
import math


def shori(H, W):
    tmp = 10000000000000
    for h in range(1, H):
        Sa = h * W
        # tatewari
        Sb = (H - h) * math.ceil(W / 2)
        Sc = (H - h) * (math.floor(W / 2))
        Sdiff_t = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
        # yokowari
        Sb = math.ceil((H - h) / 2) * W
        Sc = math.floor((H - h) / 2) * W
        Sdiff_y = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)

        min_diff = min(Sdiff_t, Sdiff_y)
        tmp = min_diff if min_diff < tmp else tmp

    return tmp


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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = 10**10
for i in range(1,H-1):
    h2 = (i+H)//2
    s1 = W*i
    s2 = W*(h2-i)
    s3 = W*(H-h2)
    tmp = max(s1,s2,s3) - min(s1,s2,s3)
    ans = min(tmp, ans)
    w = W//2
    s2 = (H-i) * w
    s3 = (H - i) * (W-w)
    tmp = max(s1,s2,s3) - min(s1,s2,s3)
    ans = min(tmp, ans)
for i in range(1,W):
    w2 = (W + i)//2
    s1 = i*H
    s2 = (w2-i)*H
    s3 = (W-w2)*H
    tmp = max(s1,s2,s3) - min(s1,s2,s3)
    ans = min(tmp, ans)

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

Submission status: Accepted

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

def check(h, w):
	if h % 3 == 0 or w % 3 == 0:
		return 0

	else:
		block1 = w * (h // 3)
		block2 = (h - (h // 3)) * (w // 2)
		block3 = h * w - block1 - block2
		gap1 = max(block1, block2, block3) - min(block1, block2, block3)

		block4 = w * (h // 3 + 1)
		block5 = (h - 1 - (h // 3)) * (w // 2)
		block6 = h * w - block4 - block5
		gap2 = max(block4, block5, block6) - min(block4, block5, block6)

		return(min(gap1, gap2, min(w, h)))

print(min(check(H, W), check(W, H)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h*w%3==0:print(0)
else:
    h1=abs((w-w//3)*(h-h//2)-min(w//3*h,(w-w//3)*(h//2)))
    h2=abs(max((w//3+1)*h,(w-w//3-1)*(h-h//2))-(w-w//3-1)*(h//2))
    w1=abs((h-h//3)*(w-w//2)-min(h//3*w,(h-h//3)*(w//2)))
    w2=abs(max((h//3+1)*w,(h-h//3-1)*(w-w//2))-(h-h//3-1)*(w//2))
    print(min(h,w,h1,h2,w1,h2))

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

h, w = nm()
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
minn = 10 ** 9
for i in range(1, w):
    if h % 2 == 0:
        minn = min(minn, max(i * h, (w - i) * h // 2)
                - min(i * h, (w - i) * h // 2))
    else:
        minn = min(minn, max(i * h, (w - i) * (h // 2), (w - i) * (h // 2 + 1))
                - min(i * h, (w - i) * (h // 2), (w - i) * (h // 2 + 1)))
for i in range(1, h):
    if w % 2 == 0:
        minn = min(minn, max(i * w, (h - i) * w // 2)
                - min(i * w, (h - i) * w // 2))
    else:
        minn = min(minn, max(i * w, (h - i) * (w // 2), (h - i) * (w // 2 + 1))
                - min(i * w, (h - i) * (w // 2), (h - i) * (w // 2 + 1)))
minn = min(minn, (h // 3 + 1) * w - (h // 3) * w, (w // 3 + 1) * h - (w // 3) * h)
print(minn)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
r=H if W%3 else 0
for i in range(1,H):
  l=[i*W, (H-i)*(W//2), (H-i)*(W-W//2)]
  m=[i*W,((H-i)//2)*W,(H-i-(H-i)//2)*W]
  r=min([r,max(l)-min(l),max(m)-min(m)])
for i in range(1,W):
  l=[i*H, (W-i)*(H//2), (W-i)*(H-H//2)]
  m=[i*H,((W-i)//2)*H,(W-i-(W-i)//2)*H]
  r=min([r,max(l)-min(l),max(m)-min(m)])
print(r)

Submission status: Accepted

Solution code:
a,b = map(int, input().split())
if a%3 == 0 or b%3 == 0:
    print(0)
else:
    #二通り考えられる
    x = a // 2
    tmp = a*b
    for i in range(b):
        s = a * (i+1)
        t = (b-i-1)*x
        u = a*b-s-t
        tmp = min(tmp,max(s,t,u)-min(s,t,u))
    y = b // 2
    tmpa = a*b
    for i in range(a):
        s = b * (i+1)
        t = (a-i-1)*y
        u = a*b-s-t
        tmpa = min(tmpa,max(s,t,u)-min(s,t,u))
    tmpb = a*b

    print(min(tmp,tmpa,a,b))

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    H,W = (int(_) for _ in input().split())

    ans = INF
    for h in range(1,H):
        if W%2 == 0:
            a= h*W//2
            b= h*W//2
        else:
            a= h*(W-1)//2
            b= h*(W+1)//2
        c= (H-h)*W
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans,s_max - s_min)

        a= h*W
        if (H-h)%2 == 0:
            b= (H-h)//2*W
            c= (H-h)//2*W
        else:
            b= (H-h-1)*W
            c= (H-h+1)*W
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans,s_max - s_min)
        
    for w in range(1,W):
        if H%2 == 0:
            a= w*H//2
            b= w*H//2
        else:
            a= w*(H-1)//2
            b= w*(H+1)//2
        c= (W-w)*H
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans,s_max - s_min)

        a= w*H
        if (W-w)%2 == 0:
            b= (W-w)//2*H
            c= (W-w)//2*H
        else:
            b= (W-w-1)//2*H
            c= (W-w+1)//2*H
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans,s_max - s_min)
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find_ds(h, w):
    ans = h * w
    if h >= 3:
        if h % 3 == 0:
            return 0
        else:
            ans = w
    for i in range(1, w):
        x0 = h * i
        x1 = h // 2 * (w - i)
        x2 = h * w - x0 - x1
        ds = max(x0, x1, x2) - min(x0, x1, x2)
        ans = min(ans, ds)
    return ans

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

Submission status: Accepted

Solution code:
tate,yoko=map(int,input().split())
#ト字型に折る
def byodo(H,W):
    bigH=H//2+H%2
    smallH=H-bigH
    todif=10**10
    for i in range(W//2+1):
        Smin=min(H*i,smallH*(W-i))
        Smax=max(H*i,bigH*(W-i))
        todif=min(todif,Smax-Smin)
    for i in range(W//2+1,W):
        Smax=H*i
        Smin=smallH*(W-i)
        todif=min(todif,Smax-Smin)
    return(todif)
def france(H,W):#III
    if W%3:
        return(H)
    else:return(0)
print(min(byodo(tate,yoko),byodo(yoko,tate),france(yoko,tate),france(tate,yoko)))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = 10**9
ans = min(ans,(h//3+min(1,h%3))*w-(h//3)*w)
ans = min(ans,(w//3+min(1,w%3))*h-(w//3)*h)
for i in range(1,h//2+1):
    s1 = i*w
    s2 = (h-i)*(w//2)
    s3 = (h-i)*(w//2+w%2)
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))
for i in range(1,w//2+1):
    s1 = i*h
    s2 = (w-i)*(h//2)
    s3 = (w-i)*(h//2+h%2)
    ans = min(ans,max(s1,s2,s3)-min(s1,s2,s3))
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def solve():
    ans = 1000000
    for i in range(2):
        if H[i] % 3 == 0:
            return 0
        ans = min(ans, H[1 - i])
        H1 = H[i] // 3
        S_max = (H1 + 1) * H[1 - i]
        S_min = (H[i] - H1 - 1) * (H[1 - i] // 2)
        ans = min(ans, S_max - S_min)
        S_min = H1 * H[1 - i]
        S_max = (H[i] - H1) * ((H[1 - i] + 1) // 2)
        ans = min(ans, S_max - S_min)
    return ans

H = list(map(int, input().split()))
print(solve())

Submission status: Accepted

Solution code:
def make_harf(H, W):
    h = H // 2
    small = W * h
    large = W * (H - h)
    w = W // 2
    small2 = w * H
    large2 = (W - w) * H
    if large - small <= large2 - small2:
        return large, small
    else:
        return large2, small2


H, W = map(int, input().split())
ans = float('inf')
for h in range(1, H):
    tmp = [h * W]
    for item in make_harf(H - h, W):
        tmp.append(item)
    ans = min(max(tmp) - min(tmp), ans)
for w in range(1, W):
    tmp = [H * w]
    for item in make_harf(H, W - w):
        tmp.append(item)
    ans = min(max(tmp) - min(tmp), ans)
print(ans)

Submission status: Accepted

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

diff = float("inf")

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

    nh = (H - h) // 2
    sb = nh * W
    sc = (H - h - nh) * W
    diff = min(diff, max(sa, sb, sc) - min(sa, sb, sc))

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

    nw = (W - w) // 2
    sb = nw * H
    sc = (W - w - nw) * H
    diff = min(diff, max(sa, sb, sc) - min(sa, sb, sc))

print(diff)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
# case 1
h1 = H / 3
h2 = (H - H / 3) / 2
h3 = H - h1 - h2
s = [h1 * W, h2 * W, h3 * W]
cand1 = max(s) - min(s)

# case 2
w1 = W / 3
w2 = (W - W / 3) / 2
w3 = W - w1 - w2
s = [w1 * H, w2 * H, w3 * H]
cand2 = max(s) - min(s)

# case 3
h1 = (W * H / 3) / W
h2 = H - h1
s = [h1 * W, h2 * W / 2, h2 * (W / 2 + W % 2)]
cand3 = max(s) - min(s)

# case 3'
h1 = (W * H / 3) / W + min(1, (W * H / 3) % W)
h2 = H - h1
s = [h1 * W, h2 * (W / 2), h2 * (W / 2 + W % 2)]
cand3d = max(s) - min(s)

# case 4
w1 = (W * H / 3) / H
w2 = W - w1
s = [w1 * H, w2 * (H / 2), w2 * (H / 2 + H % 2)]
cand4 = max(s) - min(s)

# case 4'
w1 = (W * H / 3) / H + min(1, (W * H / 3) % H)
w2 = W - w1
s = [w1 * H, w2 * (H / 2), w2 * (H / 2 + H % 2)]
cand4d = max(s) - min(s)

print min(cand1, cand2, cand3, cand3d, cand4, cand4d)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = float('inf')
for h in range(1,H):
  if (H-h)%2 == 0:
    k = max(h*W,(H-h)*W//2)-min(h*W,(H-h)*W//2)
    if ans > k:
      ans = k
  else:
    k = max(h*W,((H-h)//2)*W,((H-h)-(H-h)//2)*W)-min(h*W,((H-h)//2)*W,((H-h)-(H-h)//2)*W)
    if ans > k:
      ans = k
for w in range(1,W):
  if (W-w)%2 == 0:
    k = max(w*H,(W-w)*H//2)-min(w*H,(W-w)*H//2)
    if ans > k:
      ans = k
  else:
    k = max(w*H,((W-w)//2)*H,((W-w)-(W-w)//2)*H)-min(w*H,((W-w)//2)*H,((W-w)-(W-w)//2)*H)
    if ans > k:
      ans = k
for w in range(1,W):
  if H%2 == 0:
    l = max(w*H,(W-w)*H//2)-min(w*H,(W-w)*H//2)
    if ans > l:
      ans = l
  else:
    l = max(w*H,(W-w)*(H//2),(W-w)*(H-H//2))-min(w*H,(W-w)*(H//2),(W-w)*(H-H//2))
    if ans > l:
      ans = l
for h in range(1,H):
  if W%2 == 0:
    l = max(h*W,(H-h)*W//2)-min(h*W,(H-h)*W//2)
    if ans > l:
      ans = l
  else:
    l = max(h*W,(H-h)*(W//2),(H-h)*(W-W//2))-min(h*W,(H-h)*(W-W//2),(H-h)*(W//2))
    if ans > l:
      ans = l
print(ans)

Submission status: Accepted

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

for (h, w) in [(H, W), (W, H)]:
    for i in range(1, h):
        k, l = [], []
        k.append(w * i)
        k.append(w * ((h - i) // 2))
        k.append(w * ((h - i) - (h - i) // 2))
        l.append(w * i)
        l.append((h - i) * (w // 2))
        l.append((h - i) * (w - w // 2))
        # print(k, l, w, h - i)
        res = min(res, max(k) - min(k))
        res = min(res, max(l) - min(l))

print(res)

Submission status: Accepted

Solution code:
H, W = (int(i) for i in input().split())
ans = float("inf")
for i in range(1,H):
  a, b = (i, W)
  S = W*(H-i)
  if a%2==0 or b%2==0:
    ans = min(ans, abs(S-a*b//2))
  else:
    if a == 1 and b ==1:
      continue
    else:
      Sbig = (max(a, b)+1)*min(a, b)//2
      Ssma = (max(a, b)-1)*min(a, b)//2
      Sdiff = max(abs(S-Sbig), abs(S-Ssma), abs(Sbig-Ssma))
      ans = min(ans, Sdiff)
      
H, W = (W, H)
for i in range(1,H):
  a, b = (i, W)
  S = W*(H-i)
  if a%2==0 or b%2==0:
    ans = min(ans, abs(S-a*b//2))
  else:
    if a == 1 and b ==1:
      continue
    else:
      Sbig = (max(a, b)+1)*min(a, b)//2
      Ssma = (max(a, b)-1)*min(a, b)//2
      Sdiff = max(abs(S-Sbig), abs(S-Ssma), abs(Sbig-Ssma))
      ans = min(ans, Sdiff)
print(ans)

Submission status: Accepted

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

ans = float("inf")

for w in range(1,W-1) :
    #print("yay")
    s1 = H*w
    
    w2 = (W-w)//2
    s2 = H*w2
    s3 = H*(W-(w+w2))
    calc = max([s1,s2,s3]) - min([s1,s2,s3])
    ans = min(ans,calc)
    #print(s1,s2,s3)
    h2 = H//2
    s2 = h2*(W-w)
    s3 = (H-h2)*(W-w)
    calc = max([s1,s2,s3]) - min([s1,s2,s3])
    ans = min(ans,calc)
    #print(s1,s2,s3)

H,W = W,H    

for w in range(1,W-1) :
    #print("wow")
    s1 = H*w
    
    w2 = (W-w)//2
    s2 = H*w2
    s3 = H*(W-(w+w2))
    calc = max([s1,s2,s3]) - min([s1,s2,s3])
    ans = min(ans,calc)
    #print(s1,s2,s3)
    h2 = H//2
    s2 = h2*(W-w)
    s3 = (H-h2)*(W-w)
    calc = max([s1,s2,s3]) - min([s1,s2,s3])
    ans = min(ans,calc)
    #print(s1,s2,s3)
    
if (H == 2) and (W == 2) :
    ans = 1

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
def solve(a,b):
    if a%2==0 or b%2==0:
        return a*b//2,a*b//2
    return min(a,b)*(max(a,b)//2),min(a,b)*(1+max(a,b)//2)
ret=h*w
for x in range(1,w):
    mi,ma = solve(h,w-x)
    ret=min(ret,max([ma-mi,ma-h*x,h*x-mi]))
for x in range(1,h):
    mi,ma = solve(w,h-x)
    ret=min(ret,max([ma-mi,ma-w*x,w*x-mi]))
print(ret)

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):
  yoko = w*i
  x0 = 1
  x3 = w-1
  while x3 - x0 >2:
    x1 = (x0*2+x3)//3
    x2 =  (x0+x3*2)//3
    y1 = max(yoko,(h-i)*x1,(h-i)*(w-x1)) -min(yoko,(h-i)*x1,(h-i)*(w-x1))
    y2 = max(yoko,(h-i)*x2,(h-i)*(w-x2)) -min(yoko,(h-i)*x2,(h-i)*(w-x2))
    if y1 > y2:
      x0 = x1
    else:
      x3 = x2
  ans = min(ans,max(yoko,(h-i)*x0,(h-i)*(w-x0)) -min(yoko,(h-i)*x0,(h-i)*(w-x0)))
  x0 += 1
  if w > x0:
    ans = min(ans,max(yoko,(h-i)*x0,(h-i)*(w-x0)) -min(yoko,(h-i)*x0,(h-i)*(w-x0)))
  x0 += 1
  if w > x0:
    ans = min(ans,max(yoko,(h-i)*x0,(h-i)*(w-x0)) -min(yoko,(h-i)*x0,(h-i)*(w-x0)))

for i in range(1,w):
  yoko = h*i
  x0 = 1
  x3 = h-1
  while x3 - x0 >2:
    x1 = (x0*2+x3)//3
    x2 =  (x0+x3*2)//3
    y1 = max(yoko,(w-i)*x1,(w-i)*(h-x1)) -min(yoko,(w-i)*x1,(w-i)*(h-x1))
    y2 = max(yoko,(w-i)*x2,(w-i)*(h-x2)) -min(yoko,(w-i)*x2,(w-i)*(h-x2))
    if y1 > y2:
      x0 = x1
    else:
      x3 = x2
  ans = min(ans,max(yoko,(w-i)*x0,(w-i)*(h-x0)) -min(yoko,(w-i)*x0,(w-i)*(h-x0)))
  x0 += 1
  if w > x0:
    ans = min(ans,max(yoko,(w-i)*x0,(w-i)*(h-x0)) -min(yoko,(w-i)*x0,(w-i)*(h-x0)))
  x0 += 1
  if w > x0:
    ans = min(ans,max(yoko,(w-i)*x0,(w-i)*(h-x0)) -min(yoko,(w-i)*x0,(w-i)*(h-x0)))
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,W):
    a = i*H
    if H%2:
        b = (W-i)*(H//2)
        c = (W-i)*(H//2+1)
        tmp = max(a,b,c) - min(a,b,c)
    else:
        b = (W-i)*(H//2)
        tmp = max(a,b) - min(a,b)
    ans = min(ans, tmp)

H,W = W,H

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

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if (H*W)%3==0:
    print(0)
else:
    s=10**10
    t=10**10
    for i in range(H):
        x=max(abs(W*i-(H-i)*(W//2)),abs(W*i-(H-i)*(W//2+W%2)),(H-i)*(W%2))
        y=max(abs(W*i-W*((H-i)//2)),abs(W*i-W*((H-i)//2+(H-i)%2)),W*((H-i)%2))
        b=min(x,y)
        if b<=s:
            s=b
        else:
            break
    for j in range(W):
        v=max(abs(H*j-(W-j)*(H//2)),abs(H*j-(W-j)*(H//2+H%2)),(W-j)*(H%2))
        w=max(abs(H*j-H*((W-j)//2)),abs(H*j-H*((W-j)//2+(W-j)%2)),H*((W-j)%2))
        c=min(v,w)
        if c<=t:
            t=c
        else:
            break
    
    print(min(s,t))

Submission status: Accepted

Solution code:
from math import ceil
H,W=map(int,input().split())
ans=float("inf")
for h in range(1,H):
  m=min(h*W,(H-h)*(W//2),(H-h)*ceil(W/2))
  M=max(h*W,(H-h)*(W//2),(H-h)*ceil(W/2))
  ans=min(ans,M-m)
  m=min(h*W,((H-h)//2)*(W),ceil((H-h)/2)*(W))
  M=max(h*W,((H-h)//2)*(W),ceil((H-h)/2)*(W))
  ans=min(ans,M-m)
for w in range(1,W):
  m=min(w*H,(W-w)*(H//2),(W-w)*ceil(H/2))
  M=max(w*H,(W-w)*(H//2),(W-w)*ceil(H/2))
  ans=min(ans,M-m)
  m=min(w*H,((W-w)//2)*H,ceil((W-w)/2)*H)
  M=max(w*H,((W-w)//2)*H,ceil((W-w)/2)*H)
  ans=min(ans,M-m)
print(ans)

Submission status: Accepted

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


if not (h%3)*(w%3):
    print(0)
    exit()

def calc_T(h, w):
    bars = []
    first_cut = w//3 + w%3 - 1
    bars.append(first_cut*h)
    bars.append((h//2)*(w-first_cut))
    bars.append(h*w-sum(bars))
    return max(bars) - min(bars)

print(min(calc_T(h,w), calc_T(w,h), h, w))

Submission status: Accepted

Solution code:

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

min_score = 10**27

for i in range(1,H):
    if W%2==0:
        S1 = i*W/2
        S2 = (H-i)*W
        min_score = min(abs(S1-S2),min_score)
    else:
        S1 = i*(W-1)/2
        S2 = i*(W+1)/2
        S3 = (H-i)*W
        S4 = max(S1,S2,S3)
        S5 = min(S1,S2,S3)
        min_score = min(S4-S5,min_score)

for i in range(1,W):
    if H%2==0:
        S1 = i*H/2
        S2 = (W-i)*H
        min_score = min(abs(S1-S2),min_score)
    else:
        S1 = i*(H-1)/2
        S2 = i*(H+1)/2
        S3 = (W-i)*H
        S4 = max(S1,S2,S3)
        S5 = min(S1,S2,S3)
        min_score = min(S4-S5,min_score)

s1=int(H/3)
s2=int((H-s1)/2)
s3=H-s1-s2
S1 = max(s1*W,s2*W,s3*W)
S2 = min(s1*W,s2*W,s3*W)
min_score = min(S1-S2,min_score)

s1=int(W/3)
s2=int((W-s1)/2)
s3=W-s1-s2
S1 = max(s1*H,s2*H,s3*H)
S2 = min(s1*H,s2*H,s3*H)
min_score = min(S1-S2,min_score)

print(int(min_score))

Submission status: Accepted

Solution code:
import sys
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
if H%3 == 0 or W%3 == 0:
    print(0)
    sys.exit()
if H == 2 or W == 2:
    print(1)
    sys.exit()

a = W//3
b = W%3
c = H//3
d = H%3

ans = float('inf') 

for i in range(b+1):
    ans = min(ans,max(H*(a+i),(H//2+H%2)*(W-a-i),(H//2)*(W-a-i))-\
              min(H*(a+i),(H//2+H%2)*(W-a-i),(H//2)*(W-a-i)))
for i in range(d+1):
    ans = min(ans,max(W*(c+i),(W//2+W%2)*(H-c-i),(W//2)*(H-c-i))-\
              min(W*(c+i),(W//2+W%2)*(H-c-i),(W//2)*(H-c-i)))
print(min(ans,H,W))

Submission status: Accepted

Solution code:
import sys
import collections
import math
from collections import Counter
from collections import deque


H, W = [int(x) for x in input().split()]

ans = 10**10

# 縦切のみ 、横切のみ


def calc1(H, W):
    if H % 3 == 0:
        return 0
    else:
        return W


def calc2(H, W):
    ret = 10**10
    for w in range(1, W):
        s1 = w * H
        h = H // 2
        s2 = h * (W - w)
        s3 = (H - h) * (W - w)
        maxS = max(s1, s2, s3)
        minS = min(s1, s2, s3)
        ret = min(abs(maxS - minS), ret)
    return ret


s1 = calc1(H, W)
s2 = calc1(W, H)
s3 = calc2(H, W)
s4 = calc2(W, H)

print(min(s1, s2, s3, s4))


sys.exit(0)

Submission status: Accepted

Solution code:
a,b=map(int, input().split())
ans=a*b
if a%3==0 or b%3==0:ans=0 
if a>2:ans=min(ans,a)
if b>2:ans=min(ans,b)
for i in range(1,a):
    m=max(abs(b*i-b//2*(a-i)),abs(b//2*(a-i)-(-(-b//2)*(a-i))),abs(b*i-(-(-b//2)*(a-i))))
    ans=min(m,ans)
for i in range(1,b):
    m=max(abs(a*i-a//2*(b-i)),abs(a//2*(b-i)-(-(-a//2)*(b-i))),abs(a*i-(-(-a//2)*(b-i))))
    ans=min(m,ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H,W = map(int, input().split())

ret = 10**9
for h in range(1,H):
    w = W//2
    s1 = h*W
    s2 = (H-h)*w
    s3 = (H-h)*(W-w)
    ret = min(ret, max(s1,s2,s3)-min(s1,s2,s3))

    hh = (H-h)//2
    s1 = h*W
    s2 = hh*W
    s3 = (H-h-hh)*W
    ret = min(ret, max(s1,s2,s3)-min(s1,s2,s3))

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

    ww = (W-w)//2
    s1 = w*H
    s2 = ww*H
    s3 = (W-w-ww)*H
    ret = min(ret, max(s1,s2,s3)-min(s1,s2,s3))

print(ret)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
ans_min = 10 ** 10
if h % 3 == 0 or w % 3 == 0:
	ans_min = 0

else:
	for a in range(w+1):
		sa = h * a
		if h % 2 == 0:
			sb = (w-a) * (h // 2)
			sc = (w-a) * (h // 2)
		else:
			sb = (w-a) * (h // 2 + 1)
			sc = (w-a) * (h // 2)
		ans = max(sa,sb,sc) - min(sa,sb,sc)
		if ans_min > ans:
			ans_min = ans

	for a in range(h+1):
		sa = w * a
		if w % 2 == 0:
			sb = (h-a) * (w // 2)
			sc = (h-a) * (w // 2)
		else:
			sb = (h-a) * (w // 2 + 1)
			sc = (h-a) * (w // 2)
		ans = max(sa, sb, sc) - min(sa, sb, sc)

		if ans_min > ans:
			ans_min = ans
if ans_min > h:
	ans_min = h
if ans_min > w:
	ans_min = w
print(ans_min)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans = 10**15
import sys
if h%3==0 or w%3==0:
  print(0)
  sys.exit()
h0 = 1
while h0 <h:
  s1=h0*w
  if (h-h0)%2==0:
    s2=w*(h-h0)//2
    s3=s2
  else:
    s2=w*(h-h0)//2
    s3=w*(h-h0)//2+w
  ans1 = max(s1,s2,s3)-min(s1,s2,s3)
  if w%2==0:
    s4=(h-h0)*(w//2)
    s5=s4
  else:
    s4=(h-h0)*(w//2)
    s5=(h-h0)*(w//2)+(h-h0)
  ans2 = max(s1,s4,s5)-min(s1,s4,s5)
  ans = min(ans,ans1,ans2)
  h0 += 1
w0 = 1
while w0 <w:
  s6=w0*h
  if (w-w0)%2==0:
    s7=h*(w-w0)//2
    s8=s7
  else:
    s7=h*(w-w0)//2
    s8=h*(w-w0)//2+h
  ans3 = max(s6,s7,s8)-min(s6,s7,s8)
  if h%2==0:
    s9=(w-w0)*(h//2)
    s10=s9
  else:
    s9=(w-w0)*(h//2)
    s10=(w-w0)*(h//2)+(w-w0)
  ans4 = max(s6,s9,s10)-min(s6,s9,s10)
  ans = min(ans,ans3,ans4)
  w0 += 1
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    # 横だけ、縦だけ
    ans = min(W, H)
    for w in range(1, W):
        ans = min(ans, max(w * H, (W - w) * -(-H // 2))
                  - min(w * H, (W - w) * (H // 2)))
    for h in range(1, H):
        ans = min(ans, max(h * W, (H - h) * -(-W // 2))
                  - min(h * W, (H - h) * (W // 2)))
    print(ans)

Submission status: Accepted

Solution code:
def maxdif(a,b):
    if a % 3 == 0:
        return 0
    sabuns = []
    if a%2 == 0:
        s = a//2
        t = a//2
    else:
        s = a//2
        t = s + 1
    for i in range(b+1):
        sabun = max(abs(s*i-t*i),abs(s*i-(s+t)*(b-i)),abs(t*i-(s+t)*(b-i)))
        sabuns.append(sabun)    
    sabuns.append(b)
    return min(sabuns)


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


print(min(maxdif(H,W),maxdif(W,H)))

Submission status: Accepted

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

now = h*w
y = 1
while y < h:
    a = y*w
    if w%2 == 0:
        b = (h-y)*(w//2)
        c = (h-y)*(w//2)
    elif (h-y)%2 == 0:
        b = ((h-y)//2)*w
        c = ((h-y)//2)*w
    else:
        if (h-y) >= w:
            b = (h-y)*(w//2+1)
            c = (h-y)*(w//2)
        else:
            b = w*((h-y)//2+1)
            c = w+((h-y)//2)
    lis = [a,b,c]
    if max(lis)-min(lis) < now:
        now = max(lis)-min(lis)
    y += 1
    
x = 1
while x < w:
    a = x*h
    if h%2 == 0:
        b = (w-x)*(h//2)
        c = (w-x)*(h//2)
    elif (w-x)%2 == 0:
        b = ((w-x)//2)*h
        c = ((w-x)//2)*h
    else:
        if (w-x) >= h:
            b = ((w-x)//2)*h
            c = ((w-x)//2+1)*h
        else:
            b = (h//2+1)*(w-x)
            c = (h//2)*(w-x)
    lis = [a,b,c]
    if max(lis)-min(lis) < now:
        now = max(lis)-min(lis)
    x += 1

print(now)

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
ans = min((m%3)*n, n, (n%3)*m, m)
for i in range(1, m):
    l = [n * i, (m - i) * (n // 2), -(m - i) * (-n // 2)]
    ans = min(ans, max(l) - min(l))
n,m = m,n
for i in range(1, m):
    l = [n * i, (m - i) * (n // 2), -(m - i) * (-n // 2)]
    ans = min(ans, max(l) - min(l))
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if (H*W)%3==0:
    print(0)
    exit()
S=[H, W]
x=H//3
a=x*W;b=(H-x)*(W//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
x+=1
a=x*W;b=(H-x)*(W//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
y=W//3
a=y*H;b=(W-y)*(H//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
y+=1
a=y*H;b=(W-y)*(H//2);c=(H*W)-a-b
S.append(max([a,b,c])-min([a,b,c]))
print(min(S))

Submission status: Accepted

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

def solve(H, W):
    if H % 3 == 0:
        return 0
    result = H * W
    H1 = H // 2
    H2 = H - H1
    for x in range(W + 1):
        a = H * x
        b = (W - x) * H1
        c = (W - x) * H2
        r = max(a, c) - min(a, b)
        result = min(result, r)
        W1 = (W - x) // 2
        W2 = W - x - W1
        b = H * W1
        c = H * W2
        r = max(a, c) - min(a, b)
        result = min(result, r)
    return result

# print(H, W)

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

print(result)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def get_pattern1(H, W):
    if W%3 == 0:
        return 0
    else:
        return (H * (W/3 + 1) - H * (W/3))

def get_pattern2(H, W):
    min_S = sys.maxint
    for x in range(1, W):
        a = H * x
        b = (W - x) * (H/2)
        c = (W - x) * ((H/2) + (H %2))
        S = max(a,b,c) - min(a,b,c)
        if S < min_S:
            min_S = S
    return min_S



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] =  [long(input_raw[0]), long(input_raw[1])]
    s1 = get_pattern1(H, W)
    s2 = get_pattern2(H, W)
    s3 = get_pattern1(W, H)
    s4 = get_pattern2(W, H)
    print min(s1,s2,s3,s4)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
w, h = list(map(int, input().split()))
def solve(a, b):
  ret = float("INF")
  for i in range(a):
    s1 = b*i
    s2 = (b//2)*(a-i)
    s3 = (b-b//2)*(a-i)
    ret = min(ret, max(s1, s2, s3)-min(s1, s2, s3))
    s2 = b*((a-i)//2)
    s3 = b*((a-i)-(a-i)//2)
    ret = min(ret, max(s1, s2, s3)-min(s1, s2, s3))
  return ret
print(min(solve(w, h), solve(h, w)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=h*w
d=lambda a,b,c:max(abs(a-b),abs(b-c),abs(a-c))
def c(h,w):
 a=m
 for i in range(1,h):
  l=i*w
  y=(h-i)//2*w
  t=(h-i)*(w//2)
  a=min(a,d(l,y,m-l-y),d(l,t,m-l-t))
 return a
print(min(c(h,w),c(w,h)))

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
m = h * w
  
def d(a,b,c):
  return max(abs(a - b), abs(b - c), abs(a - c))

def c(h,w):
  a = m
  for i in range(1, h):
    l = i * w
    y = (h - i) // 2 * w
    t = (h - i) * (w // 2)
    a = min(a, d(l, y , m - l - y), d(l, t, m - l - t))
  return a

print(min(c(h, w), c(w, h)))

Submission status: Accepted

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

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    kouho.append(min(h,w)*1)
    w_small = w//2
    w_large = w-w_small
    border1 = w_large*h//(w+w_large) #ギリギリ上の四角が小さい
    h_small = h//2
    h_large = h-h_small
    border2 = h_large*w//(h+h_large)


    A1 = w*border1
    B1 = w_small*(h-border1)
    C1 = w_large*(h-border1)

    if A1 > B1:
        kouho.append(C1-B1)
    else:
        kouho.append(C1-A1)
    border1+=1
    A1 = w*border1
    B1 = w_small*(h-border1)
    C1 = w_large*(h-border1)

    kouho.append(A1-B1)

    A2 = h*border2
    B2 = h_small*(w-border2)
    C2 = h_large*(w-border2)

    if A2>B2:
        kouho.append(C2-B2)
    else:
        kouho.append(C2-A2)

    border2+=1

    A2 = h * border2
    B2 = h_small * (w - border2)
    C2 = h_large * (w - border2)

    kouho.append(A2-B2)

    #print(border1,border2)
    #print(kouho)
    print(min(kouho))

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    sq1 = (L//3+1) * S
    sq2 = (L-L//3-1)*(S//2)
    S1 = abs(sq1-sq2)
    sq3 = (L//3) * S
    sq4 = (L-L//3) * math.ceil(S/2)
    S2 = abs(sq4-sq3)
    sq5 = (S//3+1) * L
    sq6 = (S-S//3-1)*(L//2)
    S3 = abs(sq5-sq6)
    sq7 = (S//3) * L
    sq8 = (S-S//3) * math.ceil(L/2)
    S4 = abs(sq7-sq8)
    print(min(S, S1, S2, S3, S4))