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

anss = []

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

def vertical_horizontal(H,W):
    if W % 3 != 2:
        left_width = W//3
        left_area = H*left_width
        right_width = W - left_width
        if H % 2 == 0:
            right_upper_area = H//2*right_width
            right_lower_area = H//2*right_width
#             return left_area - right_upper_area
        else:
            right_upper_area = (H//2+1)*right_width
            right_lower_area = H//2*right_width
#             return max(left_area,right_upper_area) - right_lower_area
    
    if W % 3 == 2:
        left_width = W//3+1
        left_area = H*left_width
        right_width = W - left_width
        if H % 2 == 0:
            right_upper_area = H//2*right_width
            right_lower_area = H//2*right_width
#             return left_area - right_upper_area
        else:
            right_upper_area = (H//2+1)*right_width
            right_lower_area = H//2*right_width
#             return max(left_area,right_upper_area) - right_lower_area
    return (max([left_area,right_upper_area, right_lower_area])-
            min([left_area,right_upper_area, right_lower_area]))
            
anss.append(vertical_twice(H,W))
anss.append(vertical_twice(W,H))
anss.append(vertical_horizontal(H,W))
anss.append(vertical_horizontal(W,H))

print(min(anss))

Submission status: Accepted

Solution code:
import math
H,W = map(int,input().split())
ans = float('inf')
S = H*W
def minimum(x,y,z):
    S_max = max(x,y,z)
    S_min = min(x,y,z)
    return S_max-S_min
for h in range(1,H+1):
    A = h*W
    B = math.floor((H-h)/2) * W
    C = S-A-B
    ans = min(ans,minimum(A,B,C))
    
    B = (H-h)*math.floor(W/2)
    C = S-A-B
    ans = min(ans,minimum(A,B,C))

for w in range(1,W+1):
    A = H*w
    B = math.floor((W-w)/2) * H
    C = S-A-B
    ans = min(ans,minimum(A,B,C))

    B =(W-w)*math.floor(H/2)
    C = S-A-B
    ans =  min(ans,minimum(A,B,C)) 
print(ans)

Submission status: Accepted

Solution code:
h,w = sorted(list(map(int,input().split())))
if h % 3 == 0 or w % 3 == 0:
  ret = 0
else:
  c1 = ((w//3+1)*h)-((w-1-w//3)*(h//2))
  c2 = ((w-w//3)*(h-h//2))-(w//3*h)
  c3 = h
  c4 = ((h//3+1)*w)-((h-1-h//3)*(w//2))
  c5 = ((h-h//3)*(w-w//2))-(h//3*w)
  ret = min(c1,c2,c3,c4,c5)
print(ret)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = (H*W)/3
counth = 0
while counth<s:
  counth += W
if abs(counth-s) > abs(counth-s-W):
  counth -= W
Mhs = counth
counth = counth//W
H1 = H-counth
ls = [Mhs, H1*(W//2), H*W-Mhs-H1*(W//2)]
#print(ls)
ansh = [max(ls)-min(ls)]
ls = [Mhs, W*(H1//2), H*W-Mhs-W*(H1//2)]
#print(ls)
ansh += [max(ls)-min(ls)]
ansh = min(ansh)
countw = 0
while countw<s:
  countw += H
if abs(countw-s) > abs(countw-s-H):
  countw -= H
Mws = countw
countw = countw//H
W1 = W-countw
ls = [Mws, W1*(H//2), H*W-Mws-W1*(H//2)]
#print(ls)
answ = [max(ls)-min(ls)]
ls = [Mws, H*(W1//2), H*W-H*(W1//2)-Mws]
answ += [max(ls)-min(ls)]
#print(ls)
answ = min(answ)
print(min(ansh, answ))

Submission status: Accepted

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

    h1 = h // 2
    h2 = h - h1
    for w3 in range(w // 3, w // 3 + 2):
        s = [h * w3, h1 * (w - w3), h2 * (w - w3)]
        min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 2
    w2 = w - w1
    for h3 in range(h // 3, h // 3 + 2):
        s = [w * h3, w1 * (h - h3), w2 * (h - h3)]
        min_diff = min(min_diff, max(s) - min(s))

    h1 = h // 3
    h2 = (h - h1) // 2
    h3 = h - h1 - h2
    s = [w * h1, w * h2, w * h3]
    min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 3
    w2 = (w - w1) // 2
    w3 = w - w1 - w2
    s = [h * w1, h * w2, h * w3]
    min_diff = min(min_diff, max(s) - min(s))

    print(min_diff)

Submission status: Accepted

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

    h1 = h // 2
    h2 = h - h1
    for w3 in range(w // 3, w // 3 + 3):
        s = [h * w3, h1 * (w - w3), h2 * (w - w3)]
        min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 2
    w2 = w - w1
    for h3 in range(h // 3, h // 3 + 3):
        s = [w * h3, w1 * (h - h3), w2 * (h - h3)]
        min_diff = min(min_diff, max(s) - min(s))

    h1 = h // 3
    h2 = (h - h1) // 2
    h3 = h - h1 - h2
    s = [w * h1, w * h2, w * h3]
    min_diff = min(min_diff, max(s) - min(s))

    w1 = w // 3
    w2 = (w - w1) // 2
    w3 = w - w1 - w2
    s = [h * w1, h * w2, h * w3]
    min_diff = min(min_diff, max(s) - min(s))

    print(min_diff)

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

def calc(h1, h2, W):
    # 3つの領域の面積abc
    a = h1 * W
    b = h2 * (W//2)
    c = h2 * ceil(W, 2)
    return max(abs(a-b), abs(b-c), abs(c-a))

ans = INF
# 2つと1つに区切るなら、/3切り捨てか切り上げが最適のはず
h1 = H // 3
h2 = H - h1
ans = min(ans, calc(h1, h2, W))
h1 = ceil(H, 3)
h2 = H - h1
ans = min(ans, calc(h1, h2, W))

# 縦横逆もやる
H, W = W, H
h1 = H // 3
h2 = H - h1
ans = min(ans, calc(h1, h2, W))
h1 = ceil(H, 3)
h2 = H - h1
ans = min(ans, calc(h1, h2, W))

# 3つ1方向に並べるパターン
ans = min(ans, abs(ceil(W, 3)*H-W//3*H))
ans = min(ans, abs(ceil(H, 3)*W-H//3*W))

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

H, W = max(H, W), min(H, W)

a = H // 3
bc = H - a
ans1 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))
a = ceil(H, 3)
bc = H - a
ans2 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))

H, W = min(H, W), max(H, W)

a = H // 3
bc = H - a
ans3 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))
a = ceil(H, 3)
bc = H - a
ans4 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W), abs(bc*ceil(W, 2)-bc*(W//2)))

ans5 = abs(ceil(W, 3)*H-W//3*H)
ans6 = abs(ceil(H, 3)*W-H//3*W)

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

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

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

H, W = max(H, W), min(H, W)

a = H // 3
bc = H - a
ans1 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))
a = ceil(H, 3)
bc = H - a
ans2 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))

H, W = min(H, W), max(H, W)

a = H // 3
bc = H - a
ans3 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))
a = ceil(H, 3)
bc = H - a
ans4 = max(abs(bc*ceil(W, 2)-a*W), abs(bc*(W//2)-a*W))

ans5 = abs(ceil(W, 3)*H-W//3*H)
ans6 = abs(ceil(H, 3)*W-H//3*W)

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
value = H * W
#3つの長方形を(hi,wi)として考える

#h1 == H 横に3分割パターンか縦長一つ横二つパターン
#h1 + h2 = H 縦長1つ横2つパターン
#h1 + h3 = H 縦長2つ横1つパターン
##h1 + h2 + h3 = H 縦に3分割パターン

#横に3分割パターン
if W % 3 == 0:
  value = 0
else:
  value = H

#縦に3分割
if H % 3 == 0:
  value = 0
else:
  value = min(value, W)
  
#縦長一つ横二つパターン
if W % 3 != 0: #3で割り切れるならすでに上記で0になってる
  for i in range(3):
    w1 = W//3 - 1 + i
    s1 = H * w1
    w_amari = W - w1
    for j in range(3):
      h1 = H//2 - 1 + j
      s2 = h1 * w_amari
      s3 = H * W - s1 - s2
      value2 = max(s1,s2,s3) - min(s1,s2,s3)
      #print(s1,s2,s3)
      value = min(value, value2)
#縦長2つ横1つパターン      
if H % 3 != 0: #3で割り切れるならすでに上記で0になってる
  for i in range(3):
    h1 = H//3 - 1 + i
    s1 = h1 * W
    h_amari = H - h1
    for j in range(3):
      w1 = W//2 - 1 + j
      s2 = h_amari * w1
      s3 = H * W - s1 - s2
      value3 = max(s1,s2,s3) - min(s1,s2,s3)
      value = min(value, value3)
      
print(value)

Submission status: Accepted

Solution code:

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

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    if H<W:H,W = W,H
    ans = W
    S1 = 0
    for i in range(1,H+1):
        S1 += W
        S2 = (H-i) * (W//2)
        S3 = (H-i) * (W-W//2)
        tmp = max(S1,S2,S3)-min(S1,S2,S3)
        ans = min(ans,tmp)
        
    H,W = W,H
    ans = min(ans,H)
    S1 = 0
    for i in range(1,H+1):
        S1 += W
        S2 = (H-i) * (W//2)
        S3 = (H-i) * (W-W//2)
        tmp = max(S1,S2,S3)-min(S1,S2,S3)
        ans = min(ans,tmp)
    
    
    print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()

    def solve(H,W):
        ans = inf
        for h in range(H):
            if not (H-h)&1 or not W&1:
                piece = [h*W, (W*(H-h))//2]
                ans = min(ans, max(piece)-min(piece))
            else:
                if (H-h)&1:
                    piece = [h*W, ((H-h-1)*W)//2, ((H-h+1)*W)//2]
                    ans = min(ans, max(piece)-min(piece))
                if W&1:
                    piece = [h*W, ((W-1)*(H-h))//2, ((W+1)*(H-h))//2]
                    ans = min(ans, max(piece)-min(piece))
        return ans    

    ans1 = solve(H,W)
    ans2 = solve(W,H)

    print(min(ans1,ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    S = H*W

    def solve(H,W):
        ans = inf
        for h in range(H):
            if not (H-h)&1 or not W&1:
                piece = [h*W]
                piece.append(W*(H-h)/2)
                ans = min(ans, max(piece)-min(piece))
            else:
                if (H-h)&1:
                    piece = [h*W]
                    piece.append((H-h-1)*W/2)
                    piece.append((H-h+1)*W/2)
                    ans = min(ans, max(piece)-min(piece))
                if W&1:
                    piece = [h*W]
                    piece.append((W-1)*(H-h)/2)
                    piece.append((W+1)*(H-h)/2)
                    ans = min(ans, max(piece)-min(piece))
        return ans    

    ans1 = solve(H,W)
    ans2 = solve(W,H)

    print(int(min(ans1,ans2)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W = MI()
    S = H*W
    ans = inf
    for h in range(H):
        if not (H-h)&1 or not W&1:
            piece = [h*W]
            piece.append(W*(H-h)/2)
            ans = min(ans, max(piece)-min(piece))
        else:
            if (H-h)&1:
                piece = [h*W]
                piece.append((H-h-1)*W/2)
                piece.append((H-h+1)*W/2)
                ans = min(ans, max(piece)-min(piece))
            if W&1:
                piece = [h*W]
                piece.append((W-1)*(H-h)/2)
                piece.append((W+1)*(H-h)/2)
                ans = min(ans, max(piece)-min(piece))
        

    for w in range(W):
        if not (W-w)&1 or not H&1:
            piece = [w*H]
            piece.append(H*(W-w)/2)
            ans = min(ans, max(piece)-min(piece))
        else:
            if (W-w)&1:
                piece = [h*W]
                piece.append((W-w-1)*H/2)
                piece.append((W-w+1)*H/2)
                ans = min(ans, max(piece)-min(piece))
            if H&1:
                piece = [h*W]
                piece.append((H-1)*(W-w)/2)
                piece.append((H+1)*(W-w)/2)
                ans = min(ans, max(piece)-min(piece))
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = H * W
for i in range(1, H):
    maxt = W * i
    tmp1 = (H - i) * (W // 2)
    tmp2 = (H - i) * (W - (W // 2))
    ans = min(ans, (max(maxt, tmp1, tmp2) - min(maxt, tmp1, tmp2)))

    tmp3 = W * ((H - i) // 2)
    tmp4 = W * (((H - i) - ((H - i) // 2)))
    ans = min(ans, (max(maxt, tmp3, tmp4) - min(maxt, tmp3, tmp4)))

for i in range(1, W):
    maxt = H * i
    tmp1 = H * ((W - i) // 2)
    tmp2 = H * ((W - i) - ((W - i) // 2))
    ans = min(ans, (max(maxt, tmp1, tmp2) - min(maxt, tmp1, tmp2)))
    tmp3 = (W - i) * (H // 2)
    tmp4 = (W - i) * (H - (H // 2))
    ans = min(ans, (max(maxt, tmp3, tmp4) - min(maxt, tmp3, tmp4)))



print(ans)

Submission status: Accepted

Solution code:
inf = float("inf")
H, W = map(int, input().split())
ans = min(W, H)
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
for i in range(1, W):
    s = [H * i, H // 2 * (W - i), (H + 1) // 2 * (W - i)]
    ans = min(ans, abs(max(s) - min(s)))
for j in range(1, H):
    s = [W * j, W // 2 * (H - j), (W + 1) // 2 * (H - j)]
    ans = min(ans, abs(max(s) - min(s)))
print(ans)

Submission status: Accepted

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

for i in range(H):
    a = i*W
    # split vertical
    h = H-i
    w = W//2
    abc = [a, h*w, h*(W-w)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Hu",i,abc,res)
    # split holizontal
    h2 = h//2
    abc = [a, h2*W, (h-h2)*W]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Hd",i,abc,res)

for i in range(W):
    a = H*i
    # split holizontal
    h = H//2
    w = W-i
    abc = [a, h*w, (H-h)*w]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Wu",i,abc,res)
    # split vertical
    w2 = w//2
    abc = [a, H*w2, H*(w-w2)]
    if min(abc)!=0:
        res = min(res, max(abc)-min(abc))
    #print("Wd",i,abc,res)

print(res)

Submission status: Accepted

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

        print(min(self.f(H, W), self.f(W, H)))

    def f(self, H: int, W: int) -> int:
        ans = None
        for h in range(1, H):
            Sa = h * W

            half_w = W // 2
            Sb = (H - h) * half_w
            Sc = (H - h) * (W - half_w)
            S1 = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)

            half_h = (H - h) // 2
            Sb = half_h * W
            Sc = (H - h - half_h) * W
            S2 = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            S = min(S1, S2)
            if ans is None:
                ans = S
            else:
                ans = min(ans, S)
        return ans


if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

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

if H > W:
    H, W = W, H

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

ans = H

b = (H // 2)

for w in range(W+1):
    tmp_1, tmp_2, tmp_3 = H * w, b * (W-w), (H-b) * (W-w)
    tmp = max(tmp_1, tmp_2, tmp_3) - min(tmp_1, tmp_2, tmp_3)
    ans = min(ans, tmp)

d = (W // 2)
for h in range(H+1):
    tmp_1, tmp_2, tmp_3 = h*W, d * (H-h), (W-d) * (H-h)
    tmp = max(tmp_1, tmp_2, tmp_3) - min(tmp_1, tmp_2, tmp_3)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

h1 = H//3
h2 = h1 + 1
w1 = W//3
w2 = w1 + 1
hh = [h1, h2]
ww = [w1, w2]

ans = float('inf')
for i in range(2):
    s1 = hh[i] * W
    if W % 2 == 0:
        s2 = (W//2) * (H-hh[i])
        s3 = s2
    else:
        s2 = (W//2) * (H-hh[i])
        s3 = s2 + H - hh[i]
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
    if (H-hh[i]) % 2 == 0:
        s2 = ((H-hh[i])//2) * W
        s3 = s2
    else:
        s2 = ((H-hh[i])//2) * W
        s3 = s2 + W
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
    s1 = ww[i] * H
    if H % 2 == 0:
        s2 = (H//2) * (W-ww[i])
        s3 = s2
    else:
        s2 = (H//2) * (W-ww[i])
        s3 = s2 + W - ww[i]
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
    if (W-ww[i]) % 2 == 0:
        s2 = ((W-ww[i])//2) * H
        s3 = s2
    else:
        s2 = ((W-ww[i])//2) * H
        s3 = s2 + H
    ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = (int(i) for i in input().split())
    ans = 100000
    for h in range(1,H):
        s1 = set()
        s1.add(h*W)
        w = W // 2
        s1.add((H-h) * w)
        s1.add((H-h) * (W-w))
        ans1 = max(s1) - min(s1)

        s2 = set()
        s2.add(h*W)
        hb = (H-h)//2
        hc = H - h - hb
        s2.add(hb*W)
        s2.add(hc*W)
        ans2 = max(s2) - min(s2)

        ans = min(ans,ans1,ans2)

    H,W = W,H
    for h in range(1,H):
        s1 = set()
        s1.add(h*W)
        w = W // 2
        s1.add((H-h) * w)
        s1.add((H-h) * (W-w))
        ans1 = max(s1) - min(s1)

        s2 = set()
        s2.add(h*W)
        hb = (H-h)//2
        hc = H - h - hb
        s2.add(hb*W)
        s2.add(hc*W)
        ans2 = max(s2) - min(s2)

        ans = min(ans,ans1,ans2)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if h%3==0 or w%3 ==0:
    print(answer)
else:
    min1 = h*w
    min2 = h*w
    boxs = [0,0,h*w]
    for i in range(0,w):
        if h%2==0:
            boxs[0] += int(h//2)
            boxs[1] += int(h//2)
            boxs[2] -= h
            min1 = min(max(boxs)-min(boxs),min1)
        if h%2 ==1:
            boxs[0] += int(h//2)+1
            boxs[1] += int(h//2)
            boxs[2] -= h
            min1 = min(max(boxs)-min(boxs),min1)
    boxs = [0,0,h*w]      
    for i in range(0,h):
        if w%2==0:
            boxs[0] += int(w//2)
            boxs[1] += int(w//2)
            boxs[2] -= w
            min2 = min(max(boxs)-min(boxs),min2)
        if w%2 ==1:
            boxs[0] += int(w//2)+1
            boxs[1] += int(w//2)
            boxs[2] -= w
            min2 = min(max(boxs)-min(boxs),min2)
    print(min(min1,min2,h,w))

Submission status: Accepted

Solution code:

def getMinSDiff(H, W):
    Ans = H*W
    for x in range(1, W):
        # |--
        S1 = H*x
        S2 = (W - x) * (H // 2)
        S3 = H*W - (S1 + S2)
        Ans1 = max(S1, S2, S3) - min(S1, S2, S3)

        # | |
        S1 = x*H
        S2 = (W - x) // 2 * H
        S3 = H*W - (S1 + S2)
        Ans2 = max(S1, S2, S3) - min(S1, S2, S3)

        # 最小値を更新
        Ans = min(Ans, Ans1, Ans2)
    return Ans

if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    if (W % 3 == 0) or (H % 3 == 0):
        print("0")
        exit()
    else:
        Ans = min(getMinSDiff(H, W), getMinSDiff(W, H))
        print(Ans)
        exit()

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:
    ct = h
    for cy in range(1, w):
        c0 = ct * cy
        c1 = (w-cy) * (ct//2)
        c2 = h*w - c0 - c1
        cmax = max(c0, c1, c2)
        cmin = min(c0, c1, c2)
        #print(c0, c1, c2)
        if cmin > 0:
            ans = min(ans, cmax - cmin)
    ct = w
    for cy in range(1, h):
        c0 = ct * cy
        c1 = (h-cy) * (ct//2)
        c2 = h*w - c0 - c1
        cmax = max(c0, c1, c2)
        cmin = min(c0, c1, c2)
        #print(c0, c1, c2)
        if cmin > 0:
            ans = min(ans, cmax - cmin)

print(min(ans, h, w))

Submission status: Accepted

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

def split_into_two(x, y):
    if x % 2 == 0 or y % 2 == 0:
        return x*y//2, x*y//2
    else:
        if x > y:
            x, y = y, x
        return (y//2)*x, (y//2 + 1)*x

ans = h * w
for i in range(1, h//2+2):
    s0 = w*i
    s1, s2 = split_into_two(h - i, w)
    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

for i in range(1, w//2+2):
    s0 = h*i
    s1, s2 = split_into_two(h, w - i)
    ans = min(ans, max(s0, s1, s2) - min(s0, s1, s2))

print(ans)

Submission status: Accepted

Solution code:
def area(a1,a2,b):
    s1=a1*b
    if b%2==0:
        s2=a2*b//2
        s3=s2
    else:
        s2=a2*(b//2+1)
        s3=a2*(b//2)
    return max(s1,s2,s3)-min(s1,s2,s3)

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
"""
ans2_1 = 10 ** 10
ans2_2 = 10 ** 10

ans3_1 = 10 ** 10
ans3_2 = 10 ** 10
"""

ans1 = W
ans4 = H


h1 = (H + 2) // 3
h2 = H - h1
ans2_1=area(h1,h2,W)

h1 = H // 3
h2 = H - h1
ans2_2=area(h1,h2,W)

w1 = (W + 2) // 3
w2 = W - w1
ans3_1=area(w1,w2,H)

w1 = W // 3
w2 = W - w1
ans3_2=area(w1,w2,H)

print(int(min(ans1, ans2_1, ans2_2, ans3_1, ans3_2, ans4)))

Submission status: Accepted

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

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

ans2_1 = 10 ** 10
ans2_2 = 10 ** 10
ans2_3 = 10 ** 10
ans2_4 = 10 ** 10
ans3_1 = 10 ** 10
ans3_2 = 10 ** 10
ans3_3 = 10 ** 10
ans3_4 = 10 ** 10

ans1 = W
ans4 = H

h1 = (H + 2) // 3
h2 = H - h1
s1 = h1 * W
if W % 2 == 0:
    ans2_1 = abs(s1 - h2 * (W // 2))
else:
    s2 = h2 * (W // 2 + 1)
    s3 = h2 * (W // 2)
    ans2_2 = max(s1, s2, s3) - min(s1, s2, s3)

h1 = H // 3
h2 = H - h1
s1 = h1 * W
if W % 2 == 0:
    ans2_3 = abs(s1 - h2 * (W // 2))
else:
    s2 = h2 * (W // 2 + 1)
    s3 = h2 * (W // 2)
    ans2_4 = max(s1, s2, s3) - min(s1, s2, s3)

w1 = (W + 2) // 3
w2 = W - w1
s1 = H * w1
if H % 2 == 0:
    ans3_1 = abs(s1 - w2 * (H // 2))
else:
    s2 = w2 * (H // 2 + 1)
    s3 = w2 * (H // 2)
    ans3_2 = max(s1, s2, s3) - min(s1, s2, s3)

w1 = W // 3
w2 = W - w1
s1 = w1 * H
if H % 2 == 0:
    ans3_3 = abs(s1 - w2 * (H // 2))
else:
    s2 = w2 * (H // 2 + 1)
    s3 = w2 * (H // 2)
    ans3_4 = max(s1, s2, s3) - min(s1, s2, s3)

print(int(min(ans1, ans2_1, ans2_2, ans2_3, ans2_4, ans3_1, ans3_2, ans3_3, ans3_4, ans4)))

Submission status: Accepted

Solution code:
def ok_exit(res_):
    print(res_)
    exit(0)

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

res = float("inf")

# H//3
if (-(-H//3) * 3) == H:   # ceil(H//3) = -(-H//3)
    ok_exit(0)
res = min(res, W)         # W * (-(-H//3) - (H//3))

# W//3
if (-(-W//3) * 3) == W:
    ok_exit(0)
res = min(res, H)

# (W, W//2) * (H//2)
for h1 in range(1, -(-H//2)+1):
    h2 = H - h1
    A3 = (W*h1, (W//2)*h2, (W-(W//2))*h2)
    res = min(res, max(A3)-min(A3))

if res == 0:
    ok_exit(0)
if H == W:
    ok_exit(res)

# (H, H//2) * (W//2)
H, W = W, H
for h1 in range(1, -(-H//2)+1):
    h2 = H - h1
    A3 = (W*h1, (W//2)*h2, (W-(W//2))*h2)
    res = min(res, max(A3)-min(A3))

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc062/tasks/arc074_a?lang=ja
# C - Chocolate Bar

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

# 最初の長方形を決める
p_list = []
hw_list = [(H, W)]

if H != W:
    # 縦横入れ替えた場合の探索
    hw_list.append((W, H))

for hw in hw_list:
    h, w = hw
    for h_i in range(h):
        a_area = h_i * w
        # 残りの面積をなるべく均等に分ける
        # 残りを縦に割る場合
        h2, amari = divmod((h-h_i), 2)
        area_list = [a_area, h2*w, (h2+amari)*w]
        p_1 = max(area_list) - min(area_list)

        # 残りを横に割る場合
        w2, amari = divmod(w, 2)
        area_list = [a_area, (h-h_i)*w2, (h-h_i)*(w2+amari)]
        p_2 = max(area_list) - min(area_list)
        p_list.append(min(p_1, p_2))

ans = int(min(p_list))
print(ans)

Submission status: Accepted

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

# tatewari
minD = 10 ** 9
for w in range(1, W):
    s1 = w * H
    s2 = (W - w) * (H // 2)
    s3 = (W - w) * (H - H // 2)
    if s1 * s2 * s3 > 0:
        d = max(s1, s2, s3) - min(s1, s2, s3)
        if minD > d:
            minD = d
    s2 = ((W - w) // 2) * H
    s3 = (W - w - (W - w) // 2) * H
    if s1 * s2 * s3 > 0:
        d = max(s1, s2, s3) - min(s1, s2, s3)
        if minD > d:
            minD = d

# yokowari
for h in range(1, H):
    s1 = W * h
    s2 = (H - h) * (W // 2)
    s3 = (H - h) * (W - W // 2)
    if s1 * s2 * s3 > 0:
        d = max(s1, s2, s3) - min(s1, s2, s3)
        if minD > d:
            minD = d
    s2 = ((H - h) // 2) * W
    s3 = (H - h - (H - h) // 2) * W
    if s1 * s2 * s3 > 0:
        d = max(s1, s2, s3) - min(s1, s2, s3)
        if minD > d:
            minD = d

print(minD)

Submission status: Accepted

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

candidate = [
    H // 2 + W // 3 + 1,
    H // 3 + W // 2 + 1,
    H,
    W,
]
if H % 3 == 0 or W % 3 == 0:
    candidate.append(0)
if H % 2 == 0:
    candidate.append(H // 2)
if W % 2 == 0:
    candidate.append(W // 2)

print(min(candidate))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=h*w
if h==w==2:
    print(1)
    exit()
if h>2:
    t=[h//3*w,(h-(h//3))//2*w,(h-(h//3)+1)//2*w]
    t.sort()
    ans=min(ans,t[2]-t[0])
if w>2:
    t=[w//3*h,(w-(w//3))//2*h,(w-(w//3)+1)//2*h]
    t.sort()
    ans=min(ans,t[2]-t[0])
a,b=h,w
for i in range(max(1,a//3-1),min(a//2+1,a-1)):
    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
    t.sort()
    ans=min(ans,t[2]-t[0])
a,b=w,h
for i in range(max(1,a//3-1),min(a//2+1,a-1)):
    t=[i*b,(a-i)*(b//2),(a-i)*((b+1)//2)]
    t.sort()
    ans=min(ans,t[2]-t[0])
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

ans = float("inf")

if h%2==0:
    a = h//2
    b = h//2
else:
    a = h//2
    b = h//2+1

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


if w%2==0:
    a = w//2
    b = w//2
else:
    a = w//2
    b = w//2+1

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

ans = min(ans, h)
ans = min(ans, w)

print(ans)

Submission status: Accepted

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

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    temp1 = 100000000000000000
    temp2 = 100000000000000000
    for i in range(w):
        bs = [h*i,(w-i)*(h//2),(w-i)*(h//2+h%2)]
        d = max(bs)-min(bs)
        if temp1 > d :
            temp1 = d
    for i in range(h):
        bs = [w * i, (h - i) * (w // 2), (h - i) * (w // 2 + w % 2)]
        d = max(bs)-min(bs)
        if temp2 > d:
            temp2 = d
    # print(temp1,temp2)
    print(min(temp1,temp2,min(w,h)))