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())
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()

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

ans = min(H,W)

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

H,W = W,H

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

print(ans)

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))
ans = 10**10
if h%3 == 0 or w%3 == 0:
    ans = 0
else:
    h1 = h//3
    h2 = (h-h1)//2
    h3 = h-h1-h2
    ans1 = (max([h1, h2, h3]) - min(h1, h2, h3))*w

    w1 = w//3
    w2 = (w-w1)//2
    w3 = w-w1-w2
    ans2 = (max([w1, w2, w3]) - min(w1, w2, w3))*h
    
    a1 = (h//3)*w
    a2 = (w//2)*(h-h//3)
    a3 = (w-w//2)*(h-h//3)
    ans3 = max([a1, a2, a3]) - min(a1, a2, a3)
    
    a1 = (w//3)*h
    a2 = (h//2)*(w-w//3)
    a3 = (h-h//2)*(w-w//3)
    ans4 = max([a1, a2, a3]) - min(a1, a2, a3)

    a1 = (h//3+1)*w
    a2 = (w//2)*(h-h//3-1)
    a3 = (w-w//2)*(h-h//3-1)
    ans5 = max([a1, a2, a3]) - min(a1, a2, a3)
    
    a1 = (w//3+1)*h
    a2 = (h//2)*(w-w//3-1)
    a3 = (h-h//2)*(w-w//3-1)
    ans6 = max([a1, a2, a3]) - min(a1, a2, a3)
    
    ans = min([ans1, ans2, ans3, ans4, ans5, ans6])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

    ans = min(H, W)
    for y in range(H):
        a = W * y
        x = W // 2
        b = (H - y) * x
        c = (H - y) * (W - x)
        ans = min(ans, max(a, b, c) - min(a, b, c))

    for x in range(W):
        a = H * x
        y = H // 2
        b = (W - x) * y
        c = (W - x) * (H - y)
        ans = min(ans, max(a, b, c) - min(a, b, c))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
e=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)]
   e=min(e,max(l)-min(l))
print(e)

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:
na = lambda: list(map(int, input().split()))
h, w = na()
ans = 111111111111
for a, b in [(w, h), (h, w)]:
    for i in range(1, 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())
if H%3 == 0 or W%3 == 0:
    ans = 0
else:
    ans = min( max((H//3+1)*W, (H//3)*W)- min((H//3+1)*W, (H//3)*W),  max((W//3+1)*H, (W//3)*H)- min((W//3+1)*H, (W//3)*H))
    for i in range(H+1):
        ans = min( ans, max(W*i, (H-i)*(W//2), (H-i)*(W - W//2)) - min(W*i, (H-i)*(W//2), (H-i)*(W - W//2)))
    for j in range(W+1):
        ans = min( ans, max(H*j, (W-j)*(H//2), (W-j)*(H - H//2)) - min(H*j, (W-j)*(H//2), (W-j)*(H - H//2)))
print(ans)

Submission status: Accepted

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

def getMinDiff(A, B):
    if A % 3 == 0:
        return 0
    elif B % 2 == 0:
        return B // 2
    else:
        ans = B # 横3段に分ける場合の値

        # T字型に分ける場合
        for i in range(A % 3 + 1):
            A1 = A // 3 + i # 上半分の縦幅
            B1, B2 = B // 2, (B + 1) // 2 # 下半分の左側、右側の横幅
            Ss = [A1 * B, (A - A1) * B1, (A - A1) * B2]
            ans = min(ans, max(Ss) - min(Ss))
        return ans

print(min(getMinDiff(H, W), getMinDiff(W, H)))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    a = (h // 3 + 1) * w - (h - 1 - h // 3) * (w // 2)
    b = (h - h // 3) * (w - w // 2) - h // 3 * w
    c = min(h, w)
    h, w = w, h
    d = (h // 3 + 1) * w - (h - 1 - h // 3) * (w // 2)
    e = (h - h // 3) * (w - w // 2) - h // 3 * w
    print(min(a, b, c, d, e))

Submission status: Accepted

Solution code:
def calc(H, W, ans):
    w0 = W // 2
    w1 = W - w0
    for h0 in range(1, H):
        Sa = h0 * W
        h1 = H - h0
        h2 = h1 // 2
        h3 = h1 - h2
        Sb1, Sc1 = h1 * w0, h1 * w1
        Sb2, Sc2 = h2 * W, h3 * W
        m1, _, M1 = sorted([Sa, Sb1, Sc1])
        m2, _, M2 = sorted([Sa, Sb2, Sc2])
        ans = min(ans, M1 - m1, M2 - m2)
    return ans

H, W = map(int, input().split())
print(calc(W, H, calc(H, W, H * W)))

Submission status: Accepted

Solution code:
def f(ans, c_num, h, w):
    s1, s2 = divide(h, w - c_num)
    # print("ss")
    # print(s1, s2)
    return min(ans, max([c_num * h, s1, s2]) - min([c_num * h, s1, s2]))


def divide(h, w):
    if (h % 2 == 0) or (w % 2 ==0):
        return h * w // 2, h * w // 2

    else:
        return min(w, h) * (max(w, h) // 2), min(w, h) * (max(w, h) // 2 + 1)


h, w = map(int, input().split())
ideal_s = h * w // 3

ans = float("inf")
c_num = 0
count = 0

while True:
    c_num += 1
    count += h

    if count >= ideal_s:
        break

c_num_1 = c_num - 1
c_num_2 = c_num

# print(c_num_1, c_num_2)

ans = f(ans, c_num_1, h, w)
ans = f(ans, c_num_2, h, w)

hh = h
h = w
w = hh

c_num = 0
count = 0

while True:
    c_num += 1
    count += h

    if count >= ideal_s:
        break

c_num_1 = c_num - 1
c_num_2 = c_num

# print(c_num_1, c_num_2)

ans = f(ans, c_num_1, h, w)
ans = f(ans, c_num_2, h, w)

print(ans)

Submission status: Accepted

Solution code:

H, W=map(int, input().split())
deference=H*W
a=0
b=0
for i in range(W-1):
    a=H*(i+1)
    b=H//2*(W-i-1)
    if deference>max(a, b, H*W-a-b)-min(a, b, H*W-a-b):
        deference=max(a, b, H*W-a-b)-min(a, b, H*W-a-b)
for i in range(H-1):
    a=W*(i+1)
    b=W//2*(H-i-1)
    if deference>max(a, b, H*W-a-b)-min(a, b, H*W-a-b):
        deference=max(a, b, H*W-a-b)-min(a, b, H*W-a-b)
for i in range(W-2):
    a=H*(i+1)
    b=H*((W-i-1)//2)
    if deference>max(a, b, H*W-a-b)-min(a, b, H*W-a-b):
        deference=max(a, b, H*W-a-b)-min(a, b, H*W-a-b)
for i in range(H-2):
    a=W*(i+1)
    b=W*((H-i-1)//2)
    if deference>max(a, b, H*W-a-b)-min(a, b, H*W-a-b):
        deference=max(a, b, H*W-a-b)-min(a, b, H*W-a-b)
print(deference)

Submission status: Accepted

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

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

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

ans = 1e10
for i in range(1,W):
  blk1 = i * H
  # vertical cut
  if W-i >1:
    blk2 = (W-i)//2 * H
    blk3 = (W-i- (W-i)//2) * H
    #print(blk1, blk2, blk3)
    ans = min(ans, max(blk1, blk2, blk3) - min(blk1, blk2, blk3))
  # horizontal cut
  if H>1:
    blk2 = (W-i) * (H//2)
    blk3 = (W-i) * (H - (H//2))
    #print(blk1, blk2, blk3)
    ans = min(ans, max(blk1, blk2, blk3) - min(blk1, blk2, blk3))

H, W = W, H

for i in range(1,W):
  blk1 = i * H
  # vertical cut
  if W-i >1:
    blk2 = (W-i)//2 * H
    blk3 = (W-i- (W-i)//2) * H
    #print(blk1, blk2, blk3)
    ans = min(ans, max(blk1, blk2, blk3) - min(blk1, blk2, blk3))
  # horizontal cut
  if H>1:
    blk2 = (W-i) * (H//2)
    blk3 = (W-i) * (H - (H//2))
    #print(blk1, blk2, blk3)
    ans = min(ans, max(blk1, blk2, blk3) - min(blk1, blk2, blk3))

print(ans)

Submission status: Accepted

Solution code:
H, W=map(int, input().split())
m=float("inf")
for i in range(1,H):
    S1=i*W
    S2=W*((H-i)//2)
    S3=H*W-S1-S2
    if m>max(S1, S2, S3)-min(S1, S2, S3):
        m=max(S1, S2, S3)-min(S1, S2, S3)

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

    S2=(H-i)*(W//2)
    S3=H*W-S1-S2
    if m>max(S1, S2, S3)-min(S1, S2, S3):
        m=max(S1, S2, S3)-min(S1, S2, S3)
print(m)

Submission status: Accepted

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

def bisect(h, w):
    return h//2 * w, (h-h//2) * w

def solve(h, w):
    # 三
    h_3 = round(h/3)
    top = h_3*w
    middle, bottom = bisect(h-h_3, w)

    # 上部と別向き
    right, left = bisect(w, h-h_3)

    return min(
        max(top,middle,bottom) - min(top,middle,bottom),
        max(top,right,left) - min(top,right,left)
        )

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    print(min(solve(h,w), solve(w,h)))

Submission status: Accepted

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

def solve(h, w):
    # 三
    h_3 = round(h/3)
    top = h_3*w
    middle = ((h - h_3) // 2)*w
    bottom = (h - (h - h_3) // 2 - h_3)*w
    ans = max(top,middle,bottom) - min(top,middle,bottom)

    # 上部と別向き
    middle = (h-h_3)*(w//2)
    bottom = (h-h_3)*(w-w//2)

    return min(ans, max(top,middle,bottom) - min(top,middle,bottom))

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    print(min(solve(h,w), solve(w,h)))

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)
else:
  h = -(-H // 3)
  w = W // 2
  s1 = [h * W, (H - h) * w, (H - h) * (W - w)]
  d1 = max(s1) - min(s1)
  s2 = [(h - 1) * W, (H - h + 1) * w, (H - h + 1) * (W - w)]
  d2 = max(s2) - min(s2)
  h = H // 2
  w = -(-W // 3)
  s3 = [H * w, h * (W - w), (H - h) * (W - w)]
  d3 = max(s3) - min(s3)
  s4 = [H * (w - 1), h * (W - w + 1), (H - h) * (W - w + 1)]
  d4 = max(s4) - min(s4)
  print(min([d1, d2, d3, d4, H, W]))

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
# Hを３分割してH_minとH_maxを作る→H_max-H_min=1より、面積の差はW

# Wを３分割しても同様。面積の差はH
def Diff(H, W):
    # H方向に２分割してからW方向に２分割することを考える
    H_min = int(H / 3)
    H_max = int(H / 3) + 1
    #Hとして当てはまるのは上のいずれか
    W_short = int(W / 2)
    W_long = W - W_short
    S_1_1 = [H_min * W, (H - H_min) * W_short, (H - H_min) * W_long]
    S_1_2 = [H_max * W, (H - H_max) * W_short, (H - H_max) * W_long]
    D_1_1 = max(S_1_1) - min(S_1_1)
    D_1_2 = max(S_1_2) - min(S_1_2)
    return min(D_1_1, D_1_2)
R = []
R.append(H)
R.append(W)
R.append(Diff(H, W))
R.append(Diff(W, H))
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    print(min(R))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

import math

def solve(h, w):

    y = math.floor(h / 2)

    x = 1
    res = 10**12

    while x <= w / 2:
        x2 = math.floor((w - x) / 2) + x
        areas = [x * h, (x2 - x) * h, (w - x2) * h]
        areas.sort()

        diff = areas[2] - areas[0]
        if diff < res:
            res = diff

        areas = [x * h, (w - x) * y, (w - x) * (h - y)]
        areas.sort()

        diff = areas[2] - areas[0]

        if diff < res:
            res = diff
        
        x += 1

    return(res)


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

print(min(solve(h, w), solve(w, h)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split());f=lambda x:max(x)-min(x);g=lambda h,w:min([min(f([j if j else -1e9for j in[i*w,((h-i)//2)*w,((h-i)-(h-i)//2)*w]]),f([j if j else -1e9for j in[i*w,(h-i)*(w//2),(h-i)*(w-w//2)]]))for i in range(1,h)]);print(min(g(h,w),g(w,h)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
r=1e9
f=lambda x:max(x)-min(x)
for _ in 'aa':
    for i in range(1,h):r=min(min(r,f([j if j else -1e9for j in[i*w,((h-i)//2)*w,((h-i)-(h-i)//2)*w]])),f([j if j else -1e9for j in[i*w,(h-i)*(w//2),(h-i)*(w-w//2)]]))
    h,w=w,h
print(r)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
r=1e9
f=lambda x:max(x)-min(x)
for _ in 'aa':
    for i in range(1,h):
        p=[j if j else -1e9for j in[i*w,((h-i)//2)*w,((h-i)-(h-i)//2)*w]]
        q=[j if j else -1e9for j in[i*w,(h-i)*(w//2),(h-i)*(w-w//2)]]
        r=min(min(r,f(p)),f(q))
    h,w=w,h
print(r)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
res = float('inf')

# H
for i in range(1,h):
    s_h = [i * w]
    s_w = [i * w]
    # のこりは(h-i)*w
    # H
    s_h.append(((h-i)//2) * w)
    s_h.append(((h-i)-(h-i)//2) * w)
    if 0 in ((h-i)//2,((h-i)-(h-i)//2),w):
        s_h.append(float('inf'))
    #print((h-i)//2,w)
    #print(((h-i)-(h-i)//2) , w)
    #print(s_h)
    # W
    s_w.append((h-i) * (w//2))
    s_w.append((h-i) * (w - w//2))
    if 0 in ((h-i),w//2,(w-(w//2))):
        s_w.append(float('inf'))
    #print((h-i) , w//2)
    #print((h-i) , (w - w//2))
    #print(s_w)
    res_h = max(s_h) - min(s_h)
    res_w = max(s_w) - min(s_w)
    res = min(res,res_h)
    res = min(res,res_w)

# W
for i in range(1,w):
    s_h = [h * i]
    s_w = [h * i]
    # のこりはh*(w-i)
    # H
    s_h.append((h//2) * (w-i))
    s_h.append((h - (h//2)) * (w-i))
    if 0 in ((h//2),(w-i),(h-(h//2))):
        s_h.append(float('inf'))
    # W
    s_w.append(h * ((w-i)//2))
    s_w.append(h * ((w-i) - (w-i)//2))
    if 0 in (h,((w-i)//2),((w-i)-(w-i)//2)):
        s_w.append(float('inf'))
    res_h = max(s_h) - min(s_h)
    res_w = max(s_w) - min(s_w)
    res = min(res,res_h)
    res = min(res,res_w)

print(res)

Submission status: Accepted

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

# x,yの左からv列を縦に割って、左側を真ん中で横に割った時の答え
def calc(x, y, v):
    c = [v*(y//2), v*(y-y//2), (x-v)*y]
    c.sort()
    return c[2]-c[0]

# 縦横に割った時の差の最小値
def cut(x, y):
    lo = 0
    hi = x
    while hi-lo > 2:
        mid = (hi+lo)//2
        r1 = calc(x, y, mid)
        r2 = calc(x, y, mid+1)
        if r1 < r2:
            hi = mid+1
        else:
            lo = mid
    return min(calc(x, y, hi), calc(x, y, lo), calc(x, y, (hi+lo)//2))

def solve(x, y):
    # 縦横に割った時の最小値と縦だけに割った時の小さい方
    return min(cut(x, y), y)

def Solve(h, w):
    if h*w%3 == 0:
        return 0
    return min(solve(h, w), solve(w, h))

print(Solve(h, w))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(H, W):
    if H % 3 == 0 or H % 3 == 0:
        return 0

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

    def f1(L, S):
        if (math.ceil(L/3) - L/3) < (L/3 - math.floor(L/3)):
            SL = math.ceil(L/3)
        else:
            SL = math.floor(L/3)
        A = SL * S

        L -= SL
        if L < S:
            L, S = S, L

        if L % 2 == 0 or S % 2 == 0:
            B = C = (L * S) // 2
        else:
            if (math.ceil(L/2) - L/2) < (L/2 - math.floor(L/2)):
                SL = math.ceil(L/2)
            else:
                SL = math.floor(L/2)
            B = SL * S
            C = (L-SL) * S
        return max([A, B, C]) - min([A, B, C])

    def f2(L, S):
        if (math.ceil(S/3) - S/3) < (S/3 - math.floor(S/3)):
            SL = math.ceil(S/3)
        else:
            SL = math.floor(S/3)
        A = SL * L

        S -= SL
        if L < S:
            L, S = S, L

        if L % 2 == 0 or S % 2 == 0:
            B = C = (L * S) // 2
        else:
            if (math.ceil(L/2) - L/2) < (L/2 - math.floor(L/2)):
                SL = math.ceil(L/2)
            else:
                SL = math.floor(L/2)
            B = SL * S
            C = (L-SL) * S
        return max([A, B, C]) - min([A, B, C])

    return min(f1(H, W), f2(H, W))


def main():
    H, W = read_int_n()

    print(slv(H, W))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import floor, ceil

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

def solve(H: int, W: int) -> int:
    # H,Wのどちらかが3の倍数なら0
    if H % 3 == 0 or W % 3 == 0:
        return 0
    
    else:
        INF = float("inf")
        
        # [0]:タテ3分割, [1]：ヨコ3分割, [2]:T字, [3]:ト字
        ans_cand = [INF for _ in range(4)]
        
        # [0]タテ3分割
        if H < 3:
            pass
        else:
            ans_cand[0] = H
            
        # [1]ヨコ3分割
        if W < 3:
            pass
        else:
            ans_cand[1] = W
            
        # [2]T字 (floor,ceil)×(H,W)の4パターン考える
        tmp = 0
        best = INF
        
        # floor×floor
        h = floor(H/3)
        w = floor(W/2)
        
        pieces = [h*W, (H-h)*w, (H-h)*(W-w)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # floor×ceil
        h = floor(H/3)
        w = ceil(W/2)
        
        pieces = [h*W, (H-h)*w, (H-h)*(W-w)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # ceil×floor
        h = ceil(H/3)
        w = floor(W/2)
        
        pieces = [h*W, (H-h)*w, (H-h)*(W-w)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # ceil×ceil
        h = floor(H/3)
        w = floor(W/2)
        
        pieces = [h*W, (H-h)*w, (H-h)*(W-w)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        ans_cand[2] = best
          
        
        # [3]ト字 (floor,ceil)×(H,W)の4パターン考える
        tmp = 0
        best = INF
        
        # floor×floor
        w = floor(W/3)
        h = floor(H/2)
        
        pieces = [w*H, (W-w)*h, (W-w)*(H-h)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # floor×ceil
        w = floor(W/3)
        h = ceil(H/2)
        
        pieces = [w*H, (W-w)*h, (W-w)*(H-h)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # ceil×floor
        w = ceil(W/3)
        h = floor(H/2)
        
        pieces = [w*H, (W-w)*h, (W-w)*(H-h)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        # ceil×ceil
        w = ceil(W/3)
        h = ceil(H/2)
        
        pieces = [w*H, (W-w)*h, (W-w)*(H-h)]
        tmp = max(pieces) - min(pieces)
        best = min(tmp,best)
        
        ans_cand[3] = best
        
    return min(ans_cand)

ans = solve(H,W)
print(ans)

Submission status: Accepted

Solution code:
def solve(h, w):
    w1 = round(w/3)
    s1 = h*w1
    w21 = w - w1
    h2 = h//2
    s21 = h2*w21
    h3 = h - h2
    s31 = h3*w21
    ans1 = max([s1, s21, s31]) - min([s1, s21, s31])

    w22 = w21//2
    s22 = h*w22
    w32 = w - w1 - w22
    s32 = h*w32
    ans2 = max([s1, s22, s32]) - min([s1, s22, s32])

    return min(ans1, ans2)

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

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    ans1 = solve(h, w)
    ans2 = solve(w, h)
    print(min([ans1, ans2]))

Submission status: Accepted

Solution code:
import sys

def solve(h, w):
    result = h
    for i in range(1, w):
        area1 = h * i
        area2 = h // 2 * (w - i)
        area3 = h * (w - i) - area2
        diff = max(area1, area2, area3) - min(area1, area2, area3)
        result = min(result, diff)

    return result

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

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

ans = solve(H, W)
if H != W:
    ans = min(ans, solve(W, H))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w = map(int,raw_input().split())

ans = float("inf")

def div(h,w):
	def yokoyoko(a,b):
		if a != 0 and a != h and b != 0 and b!= h:
			global ans
			c = h-a-b
			ans = min(ans,max(abs(a*w-b*w),abs(a*w-c*w),abs(c*w-b*w)))

	def yokotate(a,b):
		if a != 0 and a!= h and b!= 0 and b != w:
			global ans
			tate = h-a
			ans = min(ans,max(abs(a*w-tate*b),abs(a*w-tate*(w-b)),abs(tate*b-tate*(w-b))))

	a1 = np.floor(h/3.0)

	byoko1 = np.floor((h-a1)/2.0)
	yokoyoko(a1,byoko1)

	byoko2 = np.ceil((h-a1)/2.0)
	yokoyoko(a1,byoko2)

	btate1 = np.floor(w/2.0)
	yokotate(a1,btate1)

	btate2 = np.ceil(w/2.0)
	yokotate(a1,btate2)


	a2 = np.ceil(h/3.0)

	byoko1 = np.floor((h-a2)/2.0)
	yokoyoko(a2,byoko1)

	byoko2 = np.ceil((h-a2)/2.0)
	yokoyoko(a2,byoko2)

	yokotate(a2,btate1)
	yokotate(a1,btate2)
	
div(h,w)
div(w,h)

print int(ans)

Submission status: Accepted

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    if h % 2 == 0:
        tyy1 = [(w//3) * h, (w - w//3) * h / 2]
        tyy2 = [(w//3 + 1) * h, (w - w//3 - 1) * h / 2]
    else:
        tyy1 = [(w//3) * h, (w - w//3) * (h // 2), (w - w//3) * (h // 2 + 1)]
        tyy2 = [(w//3 + 1) * h, (w - w//3 - 1) * (h // 2), (w - w//3 - 1) * (h // 2 + 1)]
    if w % 2 == 0:
        tty1 = [(h//3) * w, (h - h//3) * w / 2]
        tty2 = [(h//3 + 1) * w, (h - h//3 - 1) * w / 2]
    else:
        tty1 = [(h//3) * w, (h - h//3) * (w // 2), (h - h//3) * (w // 2 + 1)]
        tty2 = [(h//3 + 1) * w, (h - h//3 - 1) * (w // 2), (h - h//3 - 1) * (w // 2 + 1)]
    print(int(min(h, w, max(tyy1)-min(tyy1), max(tyy2)-min(tyy2), max(tty1)-min(tty1), max(tty2)-min(tty2))))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
def f(H, W):
    ans = H * W
    for h1 in range(1, H // 2 + 1):
        h2 = (H - h1) // 2
        h3 = H - h1 - h2
        ans = min(ans, max(h1, h2, h3) * W - min(h1, h2, h3) * W)

        w1 = W // 2
        w2 = W - w1
        a1 = h1 * W
        a2 = (H - h1) * w1
        a3 = (H - h1) * w2
        ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))

    return ans

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

Submission status: Accepted

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

def square(h, w, ans):
    for i in range(1, w):
        a = h * i
        b1 = ((w - i) // 2) * h
        b2 = (w - i) * (h // 2)
        c1 = ((w - i) - ((w - i) // 2)) * h
        c2 = (w - i) * (h - (h // 2))
        ans = min(ans, max([a, b1, c1]) - min([a, b1, c1]), max([a, b2, c2]) - min([a, b2, c2]))
    return ans

def main():
    h, w = map(int, input().split())
    ans = 10 ** 10
    ans = square(h, w, ans)
    ans = square(w, h, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
m=1e10
for i in range(1,a):
    l=[i*b,(a-i)*(b//2),(a-i)*(b-b//2)]
    if sum(l)==a*b:
        m=min(m,max(l)-min(l))
    o=[i*b,b*(a-i)//2,b*(a-i-(a-i)//2)]
    if sum(o)==a*b:
        m=min(m,max(o)-min(o))

for i in range(1,b):
    l=[i*a,(b-i)*(a//2),(b-i)*(a-a//2)]
    if sum(l)==a*b:
        m=min(m,max(l)-min(l))
    o=[i*a,a*(b-i)//2,a*(b-i-(b-i)//2)]
    if sum(o)==a*b:
        m=min(m,max(o)-min(o))
        
print(m)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

def check(H,W):
	ans = INF
	for i in range(1,H):
		S1 = W * i
		left = W//2
		right = W - left
		S2 = left * (H-i)
		S3 = right * (H-i)
		ans = min(max(S1,S2,S3)-min(S1,S2,S3),ans)
	return ans

if H%3 == 0 or W%3 == 0:
	print(0)
else:
	ans1 = check(H,W)
	ans2 = check(W,H)
	print(min(ans1,ans2,H,W))

Submission status: Accepted

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

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

# T字で区切るパターンを縦横それぞれ試す
mnval = float("inf")
for i in range(1,H):
    # Tの横棒に当たる方
    tmpA = i * W
    # 縦2等分
    tmpB = (H-i) * (W // 2)
    # 残り
    tmpC = H*W - tmpA - tmpB
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))
for i in range(1,W):
    tmpA = i * H
    tmpB = (W-i) * (H // 2)
    tmpC = H*W - tmpA - tmpB
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))

# 縦並び横並びパターンをそれぞれ試す
if W >= 3:
    # 3等分
    tmpA = H * (W // 3)
    # 3等分と、その余った部分の半分
    tmpB = H * (W // 3 + ((W % 3) // 2))
    # 残り
    tmpC = H*W - tmpA - tmpB
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))
if H >= 3:
    tmpA = W * (H // 3)
    tmpB = W * (H // 3 + ((H % 3) // 2))
    tmpC = H*W - tmpA - tmpB
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))

print(mnval)

Submission status: Accepted

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

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

# # どちらかの辺が3の倍数なら確実に3等分できる
# if H % 3 == 0 or W % 3 == 0:
#     print(0)
#     exit()

# T字で区切るパターンを縦横それぞれ試す
mnval = float("inf")
for i in range(1,H):
    tmpA = i * W
    tmpB = (H-i) * (W // 2)
    tmpC = (H-i) * (W // 2 + W % 2)
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))

for i in range(1,W):
    tmpA = i * H
    tmpB = (W-i) * (H // 2)
    tmpC = (W-i) * (H // 2 + H % 2)
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))

# 縦並び横並びパターンをそれぞれ試す
if W >= 3:
    tmpA = H * (W // 3)
    tmpB = H * (W // 3 + ((W % 3) // 2))
    tmpC = H * (W // 3 + ((W % 3) // 2 + (W % 3) % 2))
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))
if H >= 3:
    tmpA = W * (H // 3)
    tmpB = W * (H // 3 + ((H % 3) // 2))
    tmpC = W * (H // 3 + ((H % 3) // 2 + (H % 3) % 2))
    mnval = min(mnval, abs(max(tmpA,tmpB,tmpC) - min(tmpA,tmpB,tmpC)))

print(mnval)

Submission status: Accepted

Solution code:
from itertools import chain

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

def f(x, h, w):
    h2 = h // 2
    h3 = h - h2
    a,b,c = sorted((x,w*h2,w*h3))
    w2 = w // 2
    w3 = w - w2
    d,e,f = sorted((x,w2*h,w3*h))
    return min(c-a, f-d)

ss = ((w2*h, h, w-w2) for w2 in range(1, (w+3)//2))
ts = ((w*h2, h-h2, w) for h2 in range(1, (h+3)//2))

print(min(f(*xs) for xs in chain(ss, ts)))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if H%3==0 or W%3==0:
    print(0)
    exit()
def minAbsDiff(s,t,u):
    list=[s,t,u]
    list.sort()
    return(list[2]-list[0])
isHEven = H%2==0
isWEven = W%2==0
ans = H*W
for w in range(1,W):
    s = H*w
    if isHEven:
        t=u=(H//2)*(W-w)
    else:
        u=(H//2)*(W-w)
        t=(H//2 + 1)*(W-w)
    ans = min(ans,minAbsDiff(s,t,u))
    if (W-w)%2 ==0:
        t = u = H*(W-w)//2
    else:
        t = H*((W-w)//2)
        u = H*((W-w)//2 + 1)
    ans = min(ans,minAbsDiff(s,t,u))

for h in range(1,H):
    s = h*W
    if isWEven:
        t=u=(W//2)*(H-h)
    else:
        u=(W//2)*(H-h)
        t=(W//2 + 1)*(H-h)
    ans = min(ans,minAbsDiff(s,t,u))

    if (H-h)%2==0:
        t = u = W*(H-h)//2
    else:
        t = W*((H-h)//2)
        u = W*((H-h)//2 + 1)
    ans = min(ans,minAbsDiff(s,t,u))

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
#aaaaaa
#bbbbbb
#cccccc
x=h*w
for i in range(1,h):
    s=[w*i,w*((h-i)//2), w*(h-i-(h-i)//2)]
    if max(s)-min(s)<x:
        x=max(s)-min(s)
#aaaaaa
#bbbccc
#bbbccc
for i in range(1, h):
    s=[w*i,(h-i)*(w//2),(h-i)*(w-w//2)]
    if max(s)-min(s)<x:
        x=max(s)-min(s)
#aabbcc
#aabbcc
#aabbcc
for i in range(1,w):
    s=[h*i,h*((w-i)//2),h*(w-i-(w-i)//2)]
    if max(s)-min(s)<x:
        x=max(s)-min(s)
#aabbbb
#aacccc
#aacccc
for i in range(1, w):
    s=[h*i,(w-i)*(h//2),(w-i)*(h-h//2)]
    if max(s)-min(s)<x:
        x=max(s)-min(s)
print(x)

Submission status: Accepted

Solution code:
import math

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

# 同じ方向に三等分
ans0 = (W % 3 != 0) * H
ans1 = W * (H % 3 != 0)

blue_H = math.floor(H / 2)
i = math.floor((W * blue_H) / (H + blue_H))
ans2 = math.ceil(H / 2) * (W - i) - H * i

red_H = math.ceil(H / 2)
i = math.ceil((W * red_H) / (H + red_H))
ans3 = H * i - math.floor(H / 2) * (W - i)

blue_W = math.floor(W / 2)
i = math.floor((H * blue_W) / (W + blue_W))
ans4 = math.ceil(W / 2) * (H - i) - W * i

red_W = math.ceil(W / 2)
i = math.ceil((H * red_W) / (W + red_W))
ans5 = W * i - math.floor(W / 2) * (H - i)

ans = min(ans0, ans1, ans2, ans3, ans4, ans5)

print(ans)