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

ans = 10 ** 10
if (h % 3 == 0) or (w % 3 == 0):
    ans = 0
# 半分 or 半分+1 で切って全探索
else:
    if h % 3 == 1:
        Sa = int(h//3) * w
        Sb = int(h//3) * w
        Sc = (int(h//3)+1) * w
        dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
        ans = min(ans, dif)
    elif h % 3 == 2:
        Sa = int(h//3) * w
        Sb = (int(h//3)+1) * w
        Sc = (int(h//3)+1) * w
        dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
        ans = min(ans, dif)
    
    if w % 3 == 1:
        Sa = int(w//3) * h
        Sb = int(w//3) * h
        Sc = (int(w//3)+1) * h
        dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
        ans = min(ans, dif)
    elif w % 3 == 2:
        Sa = int(w//3) * h
        Sb = (int(w//3)+1) * h
        Sc = (int(w//3)+1) * h
        dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
        ans = min(ans, dif)

    if h % 2 == 0:
        for i in range(1,w):
            Sa = int(h/2) * i
            Sc = h * (w-i)
            dif = abs(Sa-Sc)
            ans = min(ans, dif)
    elif h % 2 == 1:
        for i in range(1,w):
            Sa = int(h // 2)  * i
            Sb = (int(h // 2) + 1) * i
            Sc = h * (w-i)
            dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            ans = min(ans, dif)
        
    if w % 2 == 0:
        for j in range(1,h):
            Sa = int(w/2) * j
            Sc = w * (h-j)
            dif = abs(Sa-Sc)
            ans = min(ans, dif)
    elif w % 2 == 1:
        for j in range(1,h):
            Sa = int(w // 2)  * j
            Sb = (int(w // 2) + 1) * j
            Sc = w * (h-j)
            dif = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            ans = min(ans, dif)
print(ans)

Submission status: Accepted

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

ans = 10**18
#fix H
for w in range(1,W):
    first_area = H*w
    if (W-w)%2 == 0:
        second_area = (W-w)*H//2
        third_area = (W-w)*H//2
    else:
        second_area = (W-w)//2*H
        third_area = (1+(W-w)//2)*H
    diff = max(first_area,second_area,third_area)-min(first_area,second_area,third_area)
    if diff < ans:
        ans = diff
    if H%2 == 0:
        second_area = H//2*(W-w)
        third_area = H//2*(W-w)
    else:
        second_area = H//2*(W-w)
        third_area = (H//2+1)*(W-w)
    diff = max(first_area,second_area,third_area)-min(first_area,second_area,third_area)
    if diff < ans:
        ans = diff
#fix W
for h in range(1,H):
    first_area = W*h
    if (H-h)%2 == 0:
        second_area = (H-h)*W//2
        third_area = (H-h)*W//2
    else:
        second_area = (H-h)//2*W
        third_area = (1+(H-h)//2)*W
    diff = max(first_area,second_area,third_area)-min(first_area,second_area,third_area)
    if diff < ans:
        ans = diff

    if W%2 == 0:
        second_area = W//2*(H-h)
        third_area = W//2*(H-h)
    else:
        second_area = W//2*(H-h)
        third_area = (W//2+1)*(H-h)
    diff = max(first_area,second_area,third_area)-min(first_area,second_area,third_area)
    if diff < ans:
        ans = diff
print(ans)

Submission status: Accepted

Solution code:
hight, width = map(int, input().split())

ans = 10 ** 18


def F(H, W):
    global ans
    for h in range(1, H):
        sa = h * W
        # 1
        h2 = (H - h) // 2
        sb = h2 * W
        sc = (H - h - h2) * W
        ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))

        # 2
        w = W // 2
        sb = (H - h) * w
        sc = (H - h) * (W - w)
        ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))


F(hight, width)
F(width, hight)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
print(min(x))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x1.sort()
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x2.sort()
    x.append(min(x1[-1]-x1[0],x2[-1]-x2[0]))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x1.sort()
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x2.sort()
    x.append(min(x1[-1]-x1[0],x2[-1]-x2[0]))
print(min(x))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x1.sort()
    x.append(x1[-1]-x1[0])
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x2.sort()
    x.append(x2[-1]-x2[0])
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x1.sort()
    x.append(x1[-1]-x1[0])
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x2.sort()
    x.append(x2[-1]-x2[0])
print(min(x))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=[]
    for i in range(1,w):
        sub=[]
        sub.append([h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)])
        #sub.append([h*i,h*((w-i)//2+1),h*(w-i)-h*((w-i)//2+1)])
        sub.append([h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)])
        #sub.append([h*i,(w-i)*(h//2+1),h*(w-i)-(w-i)*(h//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    for i in range(1,h):
        sub=[]
        sub.append([w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)])
        #sub.append([w*i,w*((h-i)//2+1),w*(h-i)-w*((h-i)//2+1)])
        sub.append([w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)])
        #sub.append([w*i,(h-i)*(w//2+1),w*(h-i)-(h-i)*(w//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    print(min(x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x,y = map(int,input().split())
if x%3 == 0 or y%3 == 0:
    print(0)
    exit()
ans = []
ans.append(x)
ans.append(y)
for x,y in (x,y),(y,x):
    a1 = x//3
    a2 = x-a1
    b1 = y//2
    b2 = y-y//2
    ans.append(max(a1*y,a2*b1,a2*b2)-min(a1*y,a2*b1,a2*b2))
    a1 = x//3+1
    a2 = x-a1
    ans.append(max(a1*y,a2*b1,a2*b2)-min(a1*y,a2*b1,a2*b2))
print(min(ans))

Submission status: Accepted

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

if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
    
def solve(a, b):
    ans = 10**15
    for i in range(1, a+1):
        s1 = i * b
        s2 = (a-i) * (b//2)
        s3 = a*b - s1 - s2
        s4 = ((a-i)//2) * b
        s5 = a*b - s1 - s4
        list1 = sorted([s1, s2, s3])
        list2 = sorted([s1, s4, s5])
        s = min((list1[-1] - list1[0]), (list2[-1] - list2[0]))
        if ans > s:
            ans = s
    return ans

print(min(solve(H, W), solve(W, H)))

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
ans1 = 10**18
ans2 = 10**18
for i in range(1, H):
  Sa = i*W
  w = int(W/2)
  Sb = (H-i)*w
  Sc = (H-i)*(W-w)
  l = [Sa, Sb, Sc]
  S1 = max(l)-min(l)
  h = int((H-i)/2)
  Sb1 = h*W
  Sc1 = ((H-i)-h)*W
  l = [Sa, Sb1, Sc1]
  S2 = max(l)-min(l)
  ans = min(S1,S2)
  ans1 = min(ans, ans1)
for i in range(1, W):
  Sa = i*H
  h = int(H/2)
  Sb = (W-i)*h
  Sc = (W-i)*(H-h)
  l = [Sa, Sb, Sc]
  S1 = max(l)-min(l)
  w = int((W-i)/2)
  Sb1 = w*H
  Sc1 = ((W-i)-w)*H
  l = [Sa, Sb1, Sc1]
  S2 = max(l)-min(l)
  ans = min(S1,S2)
  ans2 = min(ans, ans2)  
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
import math

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

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

elif h % 2 == 0 and w %2 == 0:
    if h >= w:
        side1 = int(w/2)
        diff = 1000000000000000
        for i in range(1, h):
            rect1 = side1 * i
            rect2 = w * (h - i)
            if diff > abs(rect1 - rect2):
                diff = abs(rect1 - rect2)
    else:
        side1 = int(h / 2)
        diff = 1000000000000000
        for i in range(1, w):
            rect1 = side1 * i
            rect2 = h * (w - i)
            if diff > abs(rect1 - rect2):
                diff = abs(rect1 - rect2)
    print(min(diff, diff_2))


elif h % 2 == 0 or w % 2 == 0:
    if h % 2 == 0:
        side1 = int(h/2)
        diff = 1000000000000000
        for i in range(1, w):
            rect1 = side1 * i
            rect2 = h * (w-i)
            if diff > abs(rect1 - rect2):
                diff = abs(rect1 - rect2)
                # print(i, diff)
        print(min(diff, diff_2))
    else:
        side1 = int(w / 2)
        diff = 1000000000000000
        for i in range(1, h):
            rect1 = side1 * i
            rect2 = w * (h-i)
            if diff > abs(rect1 - rect2):
                diff = abs(rect1 - rect2)
        print(min(diff, diff_2))
else:
    if h >= w:
        side1 = math.ceil(h/2)
        side2 = math.floor(h/2)
        diff = 1000000000000000
        for i in range(1, w):
            rect1 = side1 * i
            rect2 = side2 * i
            rect3 = (w-i) * h
            t = (max(rect1, rect2, rect3) - min(rect1, rect2, rect3))
            if diff > t:
                diff = t
        print(min(diff, diff_2))
    else:
        side1 = math.ceil(w/2)
        side2 = math.floor(w/2)
        diff = 1000000000000000
        for i in range(1, h):
            rect1 = side1 * i
            rect2 = side2 * i
            rect3 = (h-i) * w
            t = (max(rect1, rect2, rect3) - min(rect1, rect2, rect3))
            if diff > t:
                diff = t
        print(min(diff, diff_2))

Submission status: Accepted

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

def half(h,w):
   h1 = h//2
   h2 = h - h1
   return h1*w, h2*w
def half2(h,w):
   w1 = w//2
   w2 = w-w1
   return w1*h, w2*h

ans = float("inf")
for i in range(h):
   a = i * w
   b,c = half(h-i, w)
   tmp = max(a,b,c) - min(a,b,c)
   if a > 0 and b > 0 and c > 0:
      ans = min(tmp, ans)
   b,c = half2(h-i, w)
   tmp = max(a,b,c) - min(a,b,c)
   if a > 0 and b > 0 and c > 0:
      ans = min(tmp, ans)
   


for i in range(w):
   a = i * h
   b,c = half(h, w-i)
   tmp = max(a,b,c) - min(a,b,c)
   if a > 0 and b > 0 and c > 0:
      ans = min(tmp, ans)
   b,c = half2(h, w-i)
   tmp = max(a,b,c) - min(a,b,c)
   if a > 0 and b > 0 and c > 0:
      ans = min(tmp, ans)
   
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = 1<<60

# 3等分できたら差は0になる
if H%3==0 or W%3==0:
  print(0)
else:
  for h in range(1, H): # チョコを横置きに縦幅を探索
    A = h*W
    B = (H-h) * -(-W//2) # 切り上げ
    C = (H-h) * (W//2) # 切り捨て
    ans = min(ans, max(A,B,C) - min(A,B,C))
    
  for w in range(1, W): # チョコを縦置きに縦幅を探索
    A = w*H
    B = (W-w) * -(-H//2) # 切り上げ
    C = (W-w) * (H//2) # 切り捨て
    ans = min(ans, max(A,B,C) - min(A,B,C))
  print(min(ans, H, W))

Submission status: Accepted

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


def f(x, y):
    res = float('inf')
    w = x // 2
    for h in range(1, y):
        a = h * x
        b = (y - h) * w
        c = (y - h) * (x - w)
        s = max(a, b, c) - min(a, b, c)
        res = min(s, res)

        h2 = (y - h) // 2
        if h2 == 0:
            continue
        b = h2 * x
        c = (y - h - h2) * x
        s = max(a, b, c) - min(a, b, c)
        res = min(s, res)
    return res


ans = float('inf')
ans = min(f(W, H), ans)
ans = min(f(H, W), ans)

print(ans)

Submission status: Accepted

Solution code:
H, W=map(int, input().split())
def yyy(h, w):
  if h%3==0:
    return 0
  else:
    return w
  
def yyt(h, w):
  out=h*w
  for i in range(1, w):
    temp=[(h//2+h%2)*(w-i), (h//2)*(w-i), h*i]
    if out>max(temp)-min(temp):
      out=max(temp)-min(temp)
  return out

def tty(h, w):
  return yyt(w, h)

def ttt(h, w):
  return yyy(w, h)

print(min(yyy(H, W), yyt(H, W), tty(H, W), ttt(H, W)))

Submission status: Accepted

Solution code:
from math import floor, ceil

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


def f(H, W):
    res = 1e12
    for i in range(1, H + 1):
        a = i
        b = (H - a) // 2
        c = H - a - b
        d = max(a, b, c) - min(a, b, c)
        res = min(res, d * W)

        a = i * W
        H2 = H - i
        b = W // 2
        c = W - b
        b *= H2
        c *= H2
        d = max(a, b, c) - min(a, b, c)
        res = min(res, d)

    return res


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = MAP()

# 1方向で3つに切る
def check1(h, w):
    if h < 3:
        return INF
    if h % 3 == 0:
        return 0
    else:
        return w

# T字に切る
def check2(h, w):
    if h < 2 or w < 2:
        return INF
    res = INF
    # Tの横棒をどの位置にするか全部試す
    for i in range(1, h):
        a = i * w
        b = (h-i) * (w // 2)
        c = (h-i) * ceil(w, 2)
        res = min(res, max(a, b, c) - min(a, b, c))
    return res

# 2種類の切り方を縦横に試してみて一番小さくなるものを使う
ans = min(check1(H, W), check1(W, H), check2(H, W), check2(W, H))
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
answer=0
if not H%3==0 and not W%3==0:
  S_1=[H//3*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)]
  S_2=[(H//3+1)*W,(H-H//3-1)*(W//2),(H-H//3-1)*(W-W//2)]
  S_3=[W//3*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)]
  S_4=[(W//3+1)*H,(W-W//3-1)*(H//2),(W-W//3-1)*(H-H//2)]
  answer=min(max(S_1)-min(S_1),max(S_2)-min(S_2),max(S_3)-min(S_3),max(S_4)-min(S_4),H,W)
print(answer)

Submission status: Accepted

Solution code:

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

ans = H * W

# 1つめは縦を1ずつ増やしていく場合
for h in range(1, H):
    a = h * W

    # 残りについて、縦で分割する場合
    b = ((H - h) // 2) * W
    c = H * W - a - b
    ans = min(ans, max(a,b,c) - min(a,b,c))
    

    # 残りについて、横で分割する場合
    b = (H - h) * (W // 2)
    c = H * W - a - b
    ans = min(ans, max(a,b,c) - min(a,b,c))
    

# 1つめは横を1ずつ増やしていく場合
for w in range(1, W):
    a = w * H

    # 残りについて、縦で分割する場合
    b = (W - w) * (H//2)
    c = H * W - a - b
    ans = min(ans, max(a,b,c) - min(a,b,c))
    

    # 残りについて、横で分割する場合
    b = ((W - w) // 2) * H
    c = H * W - a - b
    ans = min(ans, max(a,b,c) - min(a,b,c))
    

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
import math
#パターン1
min1=float("inf")
i=0
while 1:
  kouho=[h*i,math.ceil(h/2)*(w-i),(h//2)*(w-i)]
  sa=max(kouho)-min(kouho)
  if sa<min1:
    min1=sa
  else:break
  i+=1

min2=float("inf")
i=0

#パターン2
while 1:
  kouho=[w*i,math.ceil(w/2)*(h-i),(w//2)*(h-i)]
  sa=max(kouho)-min(kouho)
  if sa<min2:
    min2=sa
  else:break
  i+=1

min3=w*(math.ceil(h/3)-h//3)
min4=h*(math.ceil(w/3)-w//3)


print(min(min1,min2,min3,min4))

Submission status: Accepted

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

for w1 in range(1, W//2+1):
    s1 = H*w1

    w2 = (W-w1)//2
    w3 = W-w1-w2
    s2 = H*w2
    s3 = H*w3
    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))

H, W = W, H

for w1 in range(1, W//2+1):
    s1 = H*w1

    w2 = (W-w1)//2
    w3 = W-w1-w2
    s2 = H*w2
    s3 = H*w3

    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)

Submission status: Accepted

Solution code:
import sys

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

def minimize(H, W):
    if H % 3 == 0:
        return 0
    res1 = W
    h = round(H / 3)
    w = W // 2
    block = [h * W, (H - h) * w, (H - h) * (W - w)]
    block.sort()
    res2 = block[-1] - block[0]
    return min(res1, res2)
    
def main():
    return min(minimize(H, W), minimize(W, H))

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 100000000



h, w = LI()
ans = INF
for i, j in ((h, w), (w, h)):
# iをまず分割する(h, w)
    for k in range(1, i):
        for l, m in (j, k), (k, j):
            part = [j * (i - k), l // 2 * m, (l - l // 2) * m]
            ans = min(ans, max(part) - min(part))



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 = H * W
for i in range(2):
    for h in range(1, H):
        s = [h * W, W // 2 * (H - h), (W - W // 2) * (H - h)]
        s2 = [h * W, (H - h) // 2 * W, ((H - h) - (H - h) // 2) * W]
        ans = min(ans, min(max(s) - min(s), max(s2) - min(s2)))
    H, W = W, H
print(ans)

Submission status: Accepted

Solution code:
#62c
import math
H,W = map(int, input().split())

#分け方は
#横 のみで分割
#縦 のみで分割
#縦→横 分割
#横→縦 分割　の4通り

devided = [[1,1],[1,1],[1,1]]
ans = H * W

def devision(dividend,divisor): #割られる数、割る数
    over = math.ceil(dividend/divisor)
    under = dividend//divisor
    
    if over == under:
        return over
    else:
        if abs(dividend/divisor - over) < abs(dividend/divisor - under):
            return over
        else:
            return under

        
def calc_ans(list_of_devided):   
    a = devided[0][0] * devided[0][1]
    b = devided[1][0] * devided[1][1]
    c = devided[2][0] * devided[2][1]
    #print(list_of_devided,a,b,c)
    
    if 0 in [a,b,c]:
        #print(H*W)
        return H*W
    else:
        #print(max(a,b,c) - min(a,b,c))
        return max(a,b,c) - min(a,b,c)

#横分割 ＝
devided[0][1] = W
devided[1][1] = W
devided[2][1] = W
devided[0][0] = devision(H,3)
devided[1][0] = devision(H - devided[0][0],2)
devided[2][0] = H - devided[0][0] - devided[1][0]
if ans > calc_ans(devided):
    ans = calc_ans(devided)
    
#縦分割 ||
devided[0][1] = devision(W,3)
devided[1][1] = devision(W - devided[0][1],2)
devided[2][1] = W - devided[0][1] - devided[1][1]
devided[0][0] = H
devided[1][0] = H
devided[2][0] = H
if ans > calc_ans(devided):
    ans = calc_ans(devided)
    
#縦→横 分割　├　
devided[0][1] = devision(W,3)
devided[0][0] = H
devided[1][1] = W - devided[0][1]
devided[2][1] = W - devided[0][1]
devided[1][0] = devision(H,2)
devided[2][0] = H - devided[1][0]
if ans > calc_ans(devided):
    ans = calc_ans(devided)
    
#横→縦　分割 ┬
devided[0][1] = W
devided[0][0] = devision(H,3)
devided[1][0] = H - devided[0][0]
devided[2][0] = H - devided[0][0]
devided[1][1] = devision(W,2)
devided[2][1] = W - devided[1][1]
if ans > calc_ans(devided):
    ans = calc_ans(devided)

print(ans)

Submission status: Accepted

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

ans=x*y

for i in range(1,x):
    x1=i
    
    x2=(x-x1)//2
    x3=x-x1-x2
    s1=x1*y
    s2=x2*y
    s3=x3*y
    a_yoko=max(s1,s2,s3)-min(s1,s2,s3)
    
    y2=y//2
    y3=y-y2
    x2=x-x1
    x3=x2
    y1=y
    
    s1=x1*y1
    s2=x2*y2
    s3=x3*y3
    a_tate=max(s1,s2,s3)-min(s1,s2,s3)
    
    ans=min(a_yoko,a_tate,ans)

x=w
y=h
 
for i in range(1,x):
    x1=i
    
    x2=(x-x1)//2
    x3=x-x1-x2
    s1=x1*y
    s2=x2*y
    s3=x3*y
    a_yoko=max(s1,s2,s3)-min(s1,s2,s3)
    
    y2=y//2
    y3=y-y2
    x2=x-x1
    x3=x2
    y1=y
    
    s1=x1*y1
    s2=x2*y2
    s3=x3*y3
    a_tate=max(s1,s2,s3)-min(s1,s2,s3)
    
    ans=min(a_yoko,a_tate,ans)
    
print(ans)

Submission status: Accepted

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

ans = float('inf')
if h % 3 == 0:
    ans = min(ans, 0)
else:
    ans = min(ans, w)
if w % 3 == 0:
    ans = min(ans, 0)
else:
    ans = min(ans, h)

for i in range(1, w):
    s1 = h // 2 * i
    s2 = (h - h // 2) * i
    s3 = h * (w - i)
    s = sorted([s1, s2, s3])
    ans = min(ans, s[-1] - s[0])

for i in range(1, w):
    s1 = h * i
    s2 = (h // 2) * (w - i)
    s3 = (h - h // 2) * (w - i)
    s = sorted([s1, s2, s3])
    ans = min(ans, s[-1] - s[0])

for i in range(1, h):
    s1 = w // 2 * i
    s2 = (w - w // 2) * i
    s3 = w * (h - i)
    s = sorted([s1, s2, s3])
    ans = min(ans, s[-1] - s[0])

for i in range(1, h):
    s1 = w  * i
    s2 = (w // 2) * (h - i)
    s3 = (w - w // 2) * (h - i)
    s = sorted([s1, s2, s3])
    ans = min(ans, s[-1] - s[0])

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=50000
for a,b in [(w,h),(h,w)]:
    for i in range(b):
        for c,d in [(a,b-i), (b-i,a)]:
            l=[i*a,c*(d//2),c*(d-d//2)]
            ans=min(ans,max(l)-min(l))
print(ans)

Submission status: Accepted

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

def yokowari(h, w):
  min_dfr = 10**10
  for h_wareme in range(1, h):
    rest_h = h - h_wareme
    rest_w = w
    if rest_h % 2 == 0 or rest_w % 2 == 0:
      rest_s1 = rest_h * rest_w // 2
      rest_s2 = rest_h * rest_w // 2
    elif rest_w >= rest_h:
      rest_s1 = (rest_w // 2) * rest_h
      rest_s2 = (rest_w // 2 + 1) * rest_h
    else:
      rest_s1 = (rest_h // 2) * rest_w
      rest_s2 = (rest_h // 2 + 1) * rest_w
    s = h_wareme * w
    if s == 0 or rest_s1 == 0 or rest_s2 == 0:
      continue
    dfr = max(s, rest_s1, rest_s2) - min(s, rest_s1, rest_s2)
    min_dfr = min(min_dfr, dfr)
#    print("h", h, "w", w, "hwa", h_wareme, "S", h_wareme*w, "s", rest_s1, rest_s2)
  return min_dfr

"""
def yokowari(h, w):
  o_th = h * w / 3
  print(o_th, h, o_th / h)
  h_wareme = round(o_th / h)
  rest_h = h - h_wareme
  rest_w = w
  print("", rest_h, rest_w)
  if rest_h % 2 == 0 or rest_w % 2 == 0:
    rest_s = rest_h * rest_w // 2
  elif rest_w >= rest_h:
    rest_s = (resr_w // 2) * rest_h
  else:
    rest_s = (resr_h // 2) * rest_w
  dfr = h_wareme * w - rest_s
  print(h_wareme * w, rest_s ,dfr)
  print()
  return abs(dfr)
"""
if h % 3 == 0 or w % 3 == 0:
  print(0)
  sys.exit()
else:
  print(min(yokowari(h, w), yokowari(w, h)))

Submission status: Accepted

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

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

ans=min(H,W)  #平行に3つ切るとき

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

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

print(ans)

Submission status: Accepted

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

anses=[]
for x,y in (h,w),(w,h):
  if x%3==0:
    anses.append(0)
  else:
    anses.append(y)

  for i in range(x):
    ss = (i * y, (x - i) * (y // 2), (x - i) * (y - y // 2))
    anses.append(max(ss)-min(ss))


print(min(anses))

Submission status: Accepted

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

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

Submission status: Accepted

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

mi = min(H, W)
if H % 3 == 0 or W % 3 == 0:
    mi = 0

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

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

print(mi)

Submission status: Accepted

Solution code:
#7916513 保存用
import sys

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

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

kai_1 = min(H,W)

def solve_2(a,b):
	w = a // 2
	s_l = (a-w) * b
	s_s = w * b
	s_r = 0

	tmp = s_l

	for i in range(b):
		s_r += a
		s_s -= w
		s_l -= (a-w)

		sa = max(s_r,s_s,s_l) - min(s_r,s_s,s_l)

		if tmp > sa:
			tmp = sa
			continue
		else:
			return tmp

kai_2 = solve_2(H,W)
kai_3 = solve_2(W,H)

print(min(kai_1,kai_2,kai_3))

Submission status: Accepted

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

s_org = h * w

answer = h * w
for i in range(2):
  if i == 1:
    h, w = w, h
  for height in range(1, h+1):
    s1 = height * w
    remain_height = h - height
    s2 = remain_height * int(w / 2)
    s3 = s_org - (s1 + s2)
    s_max = max([s1, s2, s3])
    s_min = min([s1, s2, s3])
    answer = min([answer, (s_max - s_min)])

    s1 = height * w
    s2 = int((h - height) / 2) * w
    s3 = s_org - (s1 + s2)
    s_max = max([s1, s2, s3])
    s_min = min([s1, s2, s3])
    answer = min([answer, (s_max - s_min)])
  
print(answer)

Submission status: Accepted

Solution code:
from math import floor, ceil

H,W = map(int,input().split())
ans = float('inf')

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

for x in range(1,H):
  S = [W*x, (H-x)*floor(W/2), (H-x)*ceil(W/2)]
  ans = min(ans, max(S)-min(S))

for x in range(1,W):
  S = [H*x, (W-x)*floor(H/2), (W-x)*ceil(H/2)]
  ans = min(ans, max(S)-min(S))

print(min(ans,H,W))

Submission status: Accepted

Solution code:
def examC(inf):
    L = LI()
    ans = inf
    for i in range(4):
        if i==0:
            for j in range(2):
                ansC = []
                if j==0:
                    cut = L[0] // 3
                    ansC.append(L[1] * cut)
                    L2 = [ L[0] - cut,L[1]]
                    cut = L2[0] // 2
                    ansC.append(L2[1] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
                else:
                    cut = L[0] // 3+1
                    ansC.append(L[1] * cut)
                    L2 = [ L[0] - cut,L[1]]
                    cut = L2[0] // 2
                    ansC.append(L2[1] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
        elif i==1:
            for j in range(2):
                ansC = []
                if j==0:
                    cut = L[0] // 3
                    ansC.append(L[1] * cut)
                    L2 = [ L[0] - cut,L[1]]
                    cut = L2[1] // 2
                    ansC.append(L2[0] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
                else:
                    cut = L[0] // 3+1
                    ansC.append(L[1] * cut)
                    L2 = [ L[0] - cut,L[1]]
                    cut = L2[1] // 2
                    ansC.append(L2[0] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
        elif i==2:
            for j in range(2):
                ansC = []
                if j==0:
                    cut = L[1] // 3
                    ansC.append(L[0] * cut)
                    L2 = [ L[0],L[1]-cut]
                    cut = L2[0] // 2
                    ansC.append(L2[1] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
                else:
                    cut = L[1] // 3+1
                    ansC.append(L[0] * cut)
                    L2 = [ L[0],L[1]-cut]
                    cut = L2[0] // 2
                    ansC.append(L2[1] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
        else:
            for j in range(2):
                ansC = []
                if j==0:
                    cut = L[1] // 3
                    ansC.append(L[0] * cut)
                    L2 = [ L[0],L[1]-cut]
                    cut = L2[1] // 2
                    ansC.append(L2[0] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
                else:
                    cut = L[1] // 3+1
                    ansC.append(L[0] * cut)
                    L2 = [ L[0],L[1]-cut]
                    cut = L2[1] // 2
                    ansC.append(L2[0] * cut)
                    ansC.append(L[1]*L[0] - sum(ansC))
                    ans = min(ans, max(ansC) - min(ansC))
    print(ans)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC(inf)