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: Time Limit Exceeded

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


slice_len = []
for i in range(H):
    slice_len.append(i+1)

slice_wid = []
for i in range(W):
    slice_wid.append(i+1)


slice_lenlen_com = (list(itertools.combinations(slice_len,2)))
slice_widwid_com = (list(itertools.combinations(slice_wid,2)))
slice_widlen_com = [(x, y) for x in slice_wid for y in slice_len]
slice_lenwid_com = [(x, y) for x in slice_len for y in slice_wid]



def get_slice():
    S = H*W
    if W % 3 == 0 or H % 3 == 0:
        S = 0

    for i in range(len(slice_lenlen_com)):
        S1 = (H - slice_lenlen_com[i][1])*W
        S2 = (slice_lenlen_com[i][1] - slice_lenlen_com[i][0])*W
        S3 = (slice_lenlen_com[i][1]- 0)*W
        if S >= max(S1,S2,S3) - min(S1,S2,S3):
            S = max(S1,S2,S3) - min(S1,S2,S3)

    for i in range(len(slice_widwid_com)):
        S1 = (W - slice_widwid_com[i][1])*H
        S2 = (slice_widwid_com[i][1] - slice_widwid_com[i][0])*H
        S3 = (slice_widwid_com[i][1]- 0)*H
        if S >= max(S1,S2,S3) - min(S1,S2,S3):
            S = max(S1,S2,S3) - min(S1,S2,S3)

    for i in range(len(slice_widlen_com)):
        S1 = slice_widlen_com[i][0] * W
        S2 = (W - slice_widlen_com[i][0]) * slice_widlen_com[i][1]
        S3 = H*W - (S1 + S2)
        if S >= max(S1,S2,S3) - min(S1,S2,S3):
            S = max(S1,S2,S3) - min(S1,S2,S3)

    for i in range(len(slice_lenwid_com)):
        S1 = slice_lenwid_com[i][0] * H
        S2 = (H - slice_lenwid_com[i][0]) * slice_lenwid_com[i][1]
        S3 = H*W - (S1 + S2)
        if S >= max(S1,S2,S3) - min(S1,S2,S3):
            S = max(S1,S2,S3) - min(S1,S2,S3)

    return S

print(get_slice())

Submission status: Time Limit Exceeded

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

def calc(big, small1, small2):
    sqs = [big, small1, small2]
    if None in sqs:
        return float("inf")
    sqs = sorted(sqs)
    return abs(sqs[0] - sqs[-1])


results = []
def sq_split(h, w, depth, target=None, target2=None):
    if depth == 2:
        # print(h, w, h*w, target, target2)
        results.append([h*w, target, target2])
    if h != 1:
        sq_split(h//2, w, depth + 1, target=((h + 1)//2) * w, target2=target)
        sq_split((h + 1)//2, w, depth + 1, target=(h//2) * w, target2=target)
    if w != 1:
        sq_split(h, w//2, depth + 1, target=h * ((w + 1) // 2), target2=target)
        sq_split(h, (w + 1)//2, depth + 1, target=h * (w//2), target2=target)

sq_split(h, w, 0)
# print(sorted(results, key=lambda x: calc(*x)))
print(sorted(map(lambda x: calc(*x), results))[0])

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, raw_input().split())
if h % 3 == 0 or w % 3 == 0:
    print 0
else:
    longer = max(h, w)
    shorter = min(h, w)
    ans = float("inf")
    for x in range(1, longer/2 + 1):
        for y in range(1, shorter/2 + 1):
            s1 = shorter * x
            s2 = (longer - x) * y
            s3 = (longer - x) * (shorter - y)
            smax = max(s1, s2, s3)
            smin = min(s1, s2, s3)
            diff = smax - smin
            if ans > diff:
                ans = diff
    print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
h,w = map(int, raw_input().split())

area = [0,0,0]
ans = 999999999999
if(h%3 == 0 or w%3 == 0):
    ans = 0
for i in range(1,h/2+1):
    area[0] = i*w
    for j in range(w/2-int(math.sqrt(w/2)),w/2+1):
        area[1] = j*(h-i)
        area[2] = (w-j)*(h-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
    
for i in range(1,w/2+1):
    area[0] = i*h
    for j in range(h/2-int(math.sqrt(h/2)),h/2+1):
        area[1] = (j)*(w-i)
        area[2] = (h-j)*(w-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a1=min(h*(w%3!=0),w*(h%3!=0))
a2=10**6
a3=10**6
for i in range(1,h):
  mx=max(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  mn=min(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  a2=min(a2,mx-mn)
for i in range(1,w):
  mx=max(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  mn=min(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  a3=min(a3,mx-mn)
print(min(a1,a2,a3))

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
ans = 10**9
for p,o in zip([h,w],[w,h]):
  for i in range(1, p//2 + 1):
    sa = i * o
    hi = (p-i)//2
    sb = o * hi
    sc = o * (p - i - hi)
    t = max(sa,sb,sc) - min(sa,sb,sc)
    ans = min(ans, t)
    
    wi = o//2
    sb = (p - i) * wi
    sc = (p - i) * (o - wi)
    t = max(sa,sb,sc) - min(sa,sb,sc)
    ans = min(ans, t)
print(ans)

Submission status: Accepted

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

hw = h * w
ans = min(h, w)
lower = (hw - ans * 2) / 3
upper = (hw + ans * 2) / 3
h_min = int((lower + w - 1) // w)
h_max = int(upper // w)
if w % 2 == 0:
    w_flg = True
else:
    w_flg = False
for hh in range(h_min - 1, h_max + 2):
    if hh < 0 or hh > h:
        continue
    s = [hh * w]
    h2 = h - hh
    if w_flg:
        s.append(h2 * (w // 2))
    else:
        s.append(h2 * (w // 2))
        s.append(h2 * ((w + 1) // 2))
    ans_sub = max(s) - min(s)
    ans = min(ans, ans_sub)

h, w = w, h    
h_min = int((lower + w - 1) // w)
h_max = int(upper // w)
if w % 2 == 0:
    w_flg = True
else:
    w_flg = False
for hh in range(h_min - 1, h_max + 2):
    if hh < 0 or hh > h:
        continue
    s = [hh * w]
    h2 = h - hh
    if w_flg:
        s.append(h2 * (w // 2))
    else:
        s.append(h2 * (w // 2))
        s.append(h2 * ((w + 1) // 2))
    ans_sub = max(s) - min(s)
    ans = min(ans, ans_sub)
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    h,w = i_map()
    if h%3 == 0 or w%3 == 0: # 綺麗に三等分できるケース
        print(0)
        exit()

    ans = INF
    th = h//2
    for i in range(1,w//2+2):
        tate = i*h
        yoko1 = (w-i)*th
        yoko2 = (w-i)*(h-th)
        M = max(tate,yoko1,yoko2)
        m = min(tate,yoko1,yoko2)
        ans = min(ans,M-m)

        amari = (w-i)//2
        yoko3 = amari*h
        yoko4 = (w-i-amari)*h
        M = max(tate,yoko3,yoko4)
        m = min(tate,yoko3,yoko4)
        ans = min(ans,M-m)

    tw = w//2
    for i in range(1,h//2+2):
        tate = i*w
        yoko1 = (h-i)*tw
        yoko2 = (h-i)*(w-tw)
        M = max(tate,yoko1,yoko2)
        m = min(tate,yoko1,yoko2)
        ans = min(ans,M-m)

        amari = (h-i)//2
        yoko3 = amari*w
        yoko4 = (h-i-amari)*w
        M = max(tate,yoko3,yoko4)
        m = min(tate,yoko3,yoko4)
        ans = min(ans,M-m)

    print(ans)


if __name__=="__main__":
    main()

Submission status: Accepted

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
ans = 10 ** 10
if h >= 3:
    ans = min(h, ans)

if w >= 3:

    ans = min(ans, w)
    # print(kouho)

for i in range(1, h):
    num1 = w * (i)
    num2 = (h - i) * (w // 2)
    num3 = (h - i) * (w - w // 2)
    kouho = [num1, num2, num3]
    kouho.sort()
    ans = min(ans, kouho[-1] - kouho[0])
for i in range(1, w):
    num1 = h * (i)
    num2 = (w - i) * (h // 2)
    num3 = (w - i) * (h - h // 2)
    kouho = [num1, num2, num3]
    kouho.sort()
    ans = min(ans, kouho[-1] - kouho[0])
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
# t字
def kawa(W, H):
    s_3 = H*W
    for h in range(1, H+1):
        s_a = h*W
        s_b = (H-h)//2 * W
        s_c = H*W - s_a - s_b
        s_3 = min(s_3, max(s_a, s_b, s_c) - min(s_a, s_b, s_c))
    return s_3

def t(W, H):
    s_t = H*W
    for h in range(1, H+1):
        s_a = h*W
        s_b = (H-h)*(W//2)
        s_c = H*W - s_a - s_b
        s_t = min(s_t, max(s_a, s_b, s_c)-min(s_a, s_b, s_c))
    return s_t

sa1 = kawa(H, W)
sa2 = kawa(W, H)
sa3 = t(W, H)
sa4 = t(H, W)
print(min(sa1, sa2, sa3, sa4))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
def f(a,b):
  c=a//3
  d=(a-c)//2
  e=a-c-d
  return(b*(e-c))
def g(a,b):
  c=a//3
  d=b//2
  s1=b*c
  s2=(a-c)*d
  s3=(a-c)*(b-d)
  S1=(max(s1,s2,s3)-min(s1,s2,s3))
  e=a//3+1
  f=b//2
  s4=e*b
  s5=(a-e)*f
  s6=(a-e)*(b-f)
  S2=(max(s4,s5,s6)-min(s4,s5,s6))
  return min(S1,S2)

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

Submission status: Accepted

Solution code:
h,w = list(map(int, input().split()))
ans = 10**10
if h%3 == 0 or w%3 == 0:
    print(0)
    exit()
    
for H in range(1, h + 1):
    a = H * w
    b = (h - H) * (w // 2)
    c = (h - H) * (w - w // 2)
    ans = min(ans, max(a,b,c) - min(a,b,c))

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

if h > 3:
    ans = min(ans, w*((h+2)//3) - w*(h//3))

if w > 3:
    ans = min(ans, h*((w+2)//3) - h*(w//3))
    
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    ans=min(h,w)
    if w%2==0:
        ans=min(ans,w//2)
    if h%2==0:
        ans=min(ans,h//2)
    if w%2==1 and h%2==1:
        H=h//2
        for x in range(w+1):
            ans=min(ans,abs(max(x*(H+1),(w-x)*h)-min(x*H,(w-x)*h)))
    print(ans)

Submission status: Accepted

Solution code:
import math

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

    candi_h = []
    candi_w = []
    if W % 2 == 0:
        candi_h.append(math.floor(H / 3))
        candi_h.append(math.ceil(H / 3))
        candi_w = [W // 2, W // 2]
    else:
        candi_h.append(math.floor(H*(W+1)/(3*W+1)))
        candi_h.append(math.ceil(H*(W+1)/(3*W+1)))
        candi_h.append(math.floor(H*(W-1)/(3*W-1)))
        candi_h.append(math.ceil(H*(W-1)/(3*W-1)))
        candi_w = [W // 2, W // 2 + 1]
    for h in candi_h:
        if h != 0:
            a1 = h * W
            a2 = (H - h) * candi_w[0]
            a3 = (H - h) * candi_w[1]
            diff = max([a1, a2, a3]) - min([a1, a2, a3])
            if diff < ans:
                ans = diff

    candi_h = []
    candi_w = []
    if H % 2 == 0:
        candi_w.append(math.floor(W / 3))
        candi_w.append(math.ceil(W / 3))
        candi_h = [H // 2, H // 2]
    else:
        candi_w.append(math.floor(W*(H+1)/(3*H+1)))
        candi_w.append(math.ceil(W*(H+1)/(3*H+1)))
        candi_w.append(math.floor(W*(H-1)/(3*H-1)))
        candi_w.append(math.ceil(W*(H-1)/(3*H-1)))
        candi_h = [H // 2, H // 2 + 1]
    for w in candi_w:
        if w != 0:
            a1 = w * H
            a2 = (W - w) * candi_h[0]
            a3 = (W - w) * candi_h[1]
            diff = max([a1, a2, a3]) - min([a1, a2, a3])
            if diff < ans:
                ans = diff

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ans = int(1e9+5)
    for i in range(h//2+1):
        a1 = i*w
        a2 = w//2*(h-i)
        a3 = (w+1)//2*(h-i)
        ans = min(ans, max(a1,a2,a3)-min(a1,a2,a3))
    for i in range(w//2+1):
        a1 = i*h
        a2 = h//2*(w-i)
        a3 = (h+1)//2*(w-i)
        ans = min(ans, max(a1,a2,a3)-min(a1,a2,a3))
    ans = min(ans, h*((w+2)//3)-h*(w//3))
    ans = min(ans, w*((h+2)//3)-w*(h//3))
    print(ans)

Submission status: Accepted

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

ans = 10**9
for i in range(1,h):
  x = h-i
  s0 = i*w
  s1 = x*(w//2)
  s2 = x*(w-w//2)
  s = max(s0,s1,s2)-min(s0,s1,s2)
  ans = min(ans,s)
  s3 = w*(x//2)
  s4 = w*(x-x//2)
  s = max(s0,s3,s4)-min(s0,s3,s4)
  ans = min(ans,s)

for i in range(1,w):
  x = w-i
  s0 = i*h
  s1 = x*(h//2)
  s2 = x*(h-h//2)
  s = max(s0,s1,s2)-min(s0,s1,s2)
  ans = min(ans,s)
  s3 = h*(x//2)
  s4 = h*(x-x//2)
  s = max(s0,s3,s4)-min(s0,s3,s4)
  ans = min(ans, s)
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

H,W=ma()
def f(H,W):
    ret=10**10+5
    for h in range(1,H):
        s1 = h*W
        s2,s3 = (H-h)//2*W,(H-h+1)//2*W
        ret=min(ret,max(s1,s2,s3) -min(s1,s2,s3) )
        s2,s3 = W//2*(H-h),(W+1)//2*(H-h)
        ret=min(ret,max(s1,s2,s3) -min(s1,s2,s3) )
    return ret
print(min(f(H,W),f(W,H)))

Submission status: Accepted

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

def abc(x,y,z): #x,y:高さまたは幅、z:ｙの幅をもつピースの高さ
    a = z * y
    if (x-z)&1 and y&1:
        b = max(x-z, y)//2 * min(x-z,y)
        c = x*y - a - b
    else:
        b = c = (x-z)*y//2
    return a, b, c

def diffS(a,b,c): #a,b,c:abc()の戻り値
    return max(a, b, c) - min(a, b, c)

def solve(x, y): #x,y:高さまたは幅
    z = x // 3
    return min(diffS(*abc(x,y,z)), diffS(*abc(x,y,z+1)))


if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    ans = min(solve(H,W), solve(W,H))
print(ans)

Submission status: Accepted

Solution code:
import sys
h, w = map(int, input().split())
if h%3==0 or w%3==0:
    print(0)
    sys.exit()
ans=h*w #inf
for i in range(1, h):
    s1=i*w
    s2=(h-i)*(w//2)
    s3=h*w-s1-s2
    now=max(s1, s2, s3)-min(s1, s2, s3)
    #print(i, now)
    ans=min(ans, now)
for j in range(1, w):
    s1=h*j
    s2=(w-j)*(h//2)
    s3=h*w-s1-s2
    now=max(s1, s2, s3)-min(s1, s2, s3)
    ans=min(ans, now)
if w>3:
    ans=min(ans, h)
if h>3:
    ans=min(ans, w)
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
ans = float("inf")

#横切れ2
if H%3==0:
    print(0)
    exit()
else:
    ans = min(ans, W)

#タテ2
if W%3==0:
    print(0)
    exit()
else:
    ans = min(ans, H)

for i in range(1, W):
    s1 = H*i
    s2 = (W-i)*(H//2)
    s3 = (W-i)*(H//2 + H%2)
    tmp = max(s1,s2,s3) - min(s1,s2,s3)
    ans = min(ans, tmp)

for i in range(1, H):
    s1 = W*i
    s2 = (H-i)*(W//2)
    s3 = (H-i)*(W//2 + W%2)
    tmp = max(s1,s2,s3) - min(s1,s2,s3)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
answer = 10**6
if H%3 == 0 or W%3 == 0:
  print(0)
else:
  # h 1 w 2
  S = H*W
  s1 = s2 = s3 = 0
  for h in range(1, H):
    s1 = h*W
    s2 = (H-h)*(W//2)
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
    s2 = ((H-h)//2)*W
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
  for w in range(1, W):
    s1 = w*H
    s2 = (W-w)*(H//2)
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
    s2 = ((W-w)//2)*H
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
  print(answer)

Submission status: Accepted

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

def hkara(h,w):
  hans = 10**9
  for i in range(1,h):
    #yoko
    fst = w*i
    snd = w//2*(h-i)
    trd = (w-w//2)*(h-i)
    mx = max(max(fst,snd),trd)
    mn = min(min(fst,snd),trd)
    hans = min(mx-mn,hans)
    #tate
    tfst = w*i
    tsnd = (h-i)//2*w
    ttrd = (h-(h-i)//2-i)*w
    tmx = max(max(tfst,tsnd),ttrd)
    tmn = min(min(tfst,tsnd),ttrd)
    hans = min(tmx-tmn,hans)
  return hans

def wkara(h,w):
  wans = 10**9
  for i in range(1,w):
    fst = h*i
    snd = h//2*(w-i)
    trd = (h-h//2)*(w-i)
    mx = max(max(fst,snd),trd)
    mn = min(min(fst,snd),trd)
    wans = min(mx-mn,wans)
    #tate
    tfst = h*i
    tsnd = (w-i)//2*h
    ttrd = (w-(w-i)//2-i)*h
    tmx = max(max(tfst,tsnd),ttrd)
    tmn = min(min(tfst,tsnd),ttrd)
    wans = min(tmx-tmn,wans)
  return wans

print(min(hkara(h,w),wkara(h,w)))

Submission status: Accepted

Solution code:
import math
h,w=map(int,input().split())
ans,cnt=h*w,0
if h%3==0 or w%3==0:
  ans=0
else:
  for i in range(1,h):
    cnt=max((h-i)*(w%2),abs(math.floor(w/2)*(h-i)-w*i),abs(math.ceil(w/2)*(h-i)-w*i))
    ans=min(ans,cnt,h,w)
  for i in range(1,w):
    cnt=max((w-i)*(h%2),abs(math.floor(h/2)*(w-i)-h*i),abs(math.ceil(h/2)*(w-i)-h*i))
    ans=min(ans,cnt,h,w)
print(ans)

Submission status: Accepted

Solution code:
import math
h,w=map(int,input().split())
ans,cnt=h*w,0
if h%3==0 or w%3==0:
  ans=0
else:
  for i in range(1,h//3+2):
    cnt=max((h-i)*(w%2),abs(math.floor(w/2)*(h-i)-w*i),abs(math.ceil(w/2)*(h-i)-w*i))
    ans=min(ans,cnt,h,w)
  for i in range(1,w//3+2):
    cnt=max((w-i)*(h%2),abs(math.floor(h/2)*(w-i)-h*i),abs(math.ceil(h/2)*(w-i)-h*i))
    ans=min(ans,cnt,h,w)
print(ans)

Submission status: Accepted

Solution code:
def cut(ch, cw):
    total = ch*cw
    if not ch % 2 or not cw % 2:
        x = ch*cw // 2
        return x, x
    else:
        x = max(ch*(cw//2), cw*(ch//2))
        return x, total - x


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

ans = h*w

for i in range(2):
    yh = h // 3 + i
    s = [yh*w]
    ch = h - yh
    s += cut(ch, w)
    ans = min(ans, max(s) - min(s))

for i in range(2):
    yw = w // 3 + i
    s = [h*yw]
    cw = w - yw
    s += cut(h, cw)
    ans = min(ans, max(s) - min(s))

print(ans)

Submission status: Accepted

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

inf=float('inf')

ans=inf

for i in range(1,h):
  a=i*w
  rest=h*w-a
  b=(w//2)*(h-i)
  c=rest-b
  max_s=max(a,b,c)
  min_s=min(a,b,c)
  ans=min(ans,max_s-min_s)
  
for j in range(1,w):
  A=j*h
  Rest=h*w-A
  B=(h//2)*(w-j)
  C=Rest-B
  Max_s=max(A,B,C)
  Min_s=min(A,B,C)
  ans=min(ans,Max_s-Min_s)
  
if w>=3:
  if w%3==0:
    ans=0
  else:
    ans=min(ans,h)
    
if h>=3:
  if h%3==0:
    ans=0
  else:
    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)
    exit()

def solve2(h, w):
    if h % 2 == 0 or w % 2 == 0:
        return [h*w // 2]
    elif h < w:
        return [h * (w//2), h * (w//2 + 1)]
    else:
        return [w * (h//2), w * (h//2 + 1)]

def solve1(h, w):
    ans = []
    ans.append(max([(h//3) * w] + solve2(h - h//3, w)) - min([(h//3) * w] + solve2(h - h//3, w)))
    ans.append(max([(h//3 + 1) * w] + solve2(h - h//3 - 1, w)) - min([(h//3 + 1) * w] + solve2(h - h//3 - 1, w)))
    return min(ans)

print(min([solve1(h, w), solve1(w, h)]))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
Min = float('inf')
if H >= 3:
    if H%3 == 0:
        Min = 0
    Min = min(Min, W)
if W>=3:
    if W%3 == 0:
        Min = 0
    Min = min(Min, H)

for h in range(1,H):
    cake1 = h*W
    cake2 = (H-h)*(W//2)
    cake3 = (H-h)*(-(-W//2))
    big = max(cake1,cake2,cake3)
    small = min(cake1,cake2,cake3)
    Min = min(Min,big-small)


for w in range(1,W):
    cake1 = w*H
    cake2 = (W-w)*(H//2)
    cake3 = (W-w)*(-(-H//2))
    big = max(cake1,cake2,cake3)
    small = min(cake1,cake2,cake3)
    Min = min(Min,big-small)

print(Min)

Submission status: Accepted

Solution code:
import math

def main():
	H, W = [int(a) for a in input().split(" ")]

	cand = []
	# case 1. w 3 split, h 3 split
	if W % 3 == 0 or H % 3 == 0:
		print(0)
		return 0
	# W % 3 !== 0 and H % 3 !== 0
	cand.append(H)
	cand.append(W)
	# case 2. w split -> h split
	cand += split_3(H, W)
	cand += split_3(W, H)

	print(min(cand))
	return 0

def split_3(a, b):
	a_f = math.floor(a/3)
	a_c = math.ceil(a/3)
	b_f = math.floor(b/2)
	b_c = math.ceil(b/2)

	a1 = [b * a_f, (a - a_f) * b_f, a * b - (a - a_f) * b_f - b * a_f]
	a2 = [b * a_c, (a - a_c) * b_f, a * b - (a - a_c) * b_f - b * a_c]
	a3 = [b * a_f, (a - a_f) * b_c, a * b - (a - a_f) * b_c - b * a_f]
	a4 = [b * a_c, (a - a_c) * b_c, a * b - (a - a_c) * b_c - b * a_c]

	return [max(a1) - min(a1), max(a2) - min(a2), max(a3) - min(a3), max(a4) - min(a4)]

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int,readline().split())
INF = 10**31
ans = INF

# 横二回切る S1,Sw2,Sw3 Sw_min,Sw_max
# 横一回、縦一回 S1,Sh2,Sh3 Sh_min,Sh_max
def solve(H,W,ans):
    for i in range(1,H):
        S1 = i*W
        rem = H - i
        Sw2 = rem // 2 * W 
        Sw3 = (rem - rem // 2) * W
        Sw_min = min(S1,Sw2,Sw3) 
        Sw_max = max(S1,Sw2,Sw3)
        Sh2 = W // 2 *rem
        Sh3 = (W - W // 2) * rem
        Sh_min = min(S1,Sh2,Sh3)
        Sh_max = max(S1,Sh2,Sh3)
        ans = min(Sw_max-Sw_min,Sh_max-Sh_min,ans)
    return ans

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = float('inf')
# 縦
for i in range(1, W):
  a = H*i
  bc = H*(W-i)
  b = (H//2) * (W-i)
  c = bc-b
  mx = max([a, b, c])
  mn = min([a, b, c])
  ans = min(ans, (mx-mn))

  bb = H * ((W-i)//2)
  cc = bc-bb
  mx = max([a, bb, cc])
  mn = min([a, bb, cc])
  ans = min(ans, (mx-mn))

# 横
for i in range(1, H):
  a = i*W
  bc = (H-i)*W
  b = (H-i) * (W//2)
  c = bc-b
  mx = max([a, b, c])
  mn = min([a, b, c])
  ans = min(ans, (mx-mn))

  bb = ((H-i)//2) * (W)
  cc = bc-bb
  mx = max([a, bb, cc])
  mn = min([a, bb, cc])
  ans = min(ans, (mx-mn))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class V:
    def __init__(self, f, v = None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def __call__(self, n):
        if n is None:
            return self.v

        if self.v is None:
            self.v = n
            return self.v
        self.v = self.f(self.v, n) 

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

def minmax(*args):
    return max(args) - min(args)

def sep(m, n):
    a = b = c = 0
    nn = n // 2
    ans = V(min, float("inf"))

    for i in range(1, m):
        a = i * n
        mm = (m - i) // 2
    
        # 横
        b, c = (m - i) * nn, (m - i) * (n - nn)
        ans(minmax(a, b, c))

        # 縦
        b, c = mm * n, (m - i - mm) * n
        ans(minmax(a, b, c))
    
    return ans.v

print(min(sep(h, w), sep(w, h)))

Submission status: Accepted

Solution code:
# 素直に全探索したほうが楽
H,W = (int(T) for T in input().split())
minSH = H*W
minSW = H*W
for TH in range(1,H):
    BlockA = TH*W

    if TH<=(H-2):
        BlockB1 = ((H-TH)//2)*W
        BlockC1 = H*W-(BlockA+BlockB1)
        BigSCa1 = max(BlockA,BlockB1,BlockC1)
        SmlSCa1 = min(BlockA,BlockB1,BlockC1)
        DifSCa1 = BigSCa1-SmlSCa1
    else:
        DifSCa1 = H*W

    if W>=2:
        BlockB2 = (H-TH)*(W//2)
        BlockC2 = H*W-(BlockA+BlockB2)
        BigSCa2 = max(BlockA,BlockB2,BlockC2)
        SmlSCa2 = min(BlockA,BlockB2,BlockC2)
        DifSCa2 = BigSCa2-SmlSCa2
    else:
        DifSCa2 = H*W

    if min(DifSCa1,DifSCa2)<minSH:
        minSH = min(DifSCa1,DifSCa2)

for TW in range(1,W):
    BlockA = H*TW

    if TW<=(W-2):
        BlockB1 = H*((W-TW)//2)
        BlockC1 = H*W-(BlockA+BlockB1)
        BigSCa1 = max(BlockA,BlockB1,BlockC1)
        SmlSCa1 = min(BlockA,BlockB1,BlockC1)
        DifSCa1 = BigSCa1-SmlSCa1
    else:
        DifSCa1 = H*W

    if H>=2:
        BlockB2 = (H//2)*(W-TW)
        BlockC2 = H*W-(BlockA+BlockB2)
        BigSCa2 = max(BlockA,BlockB2,BlockC2)
        SmlSCa2 = min(BlockA,BlockB2,BlockC2)
        DifSCa2 = BigSCa2-SmlSCa2
    else:
        DifSCa2 = H*W

    if min(DifSCa1,DifSCa2)<minSW:
        minSW = min(DifSCa1,DifSCa2)

print(min(minSH,minSW))

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = float('inf')
for h in range(1,H):
    S = [h * W]
    w = W // 2
    S += [(H-h) * w]
    S += [(H-h) * (W-w)]
    ans = min(ans,max(S)-min(S))

for h in range(1,H):
    S = [h * W]
    hb = (H-h) // 2
    S += [hb * W]
    S += [(H-h-hb) * W]
    ans = min(ans,max(S)-min(S))

for w in range(1,W):
    S = [H * w]
    h = H // 2
    S += [h * (W-w)]
    S += [(H-h) * (W-w)]
    ans = min(ans,max(S)-min(S))

for w in range(1,W):
    S = [w * H]
    wb = (W-w) // 2
    S += [wb * H]
    S += [(W-w-wb) * H]
    ans = min(ans,max(S)-min(S))

print(ans)

Submission status: Accepted

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

for h in range(1,H):
    Sa = h * W
    hb = (H-h) // 2
    Sb = hb * W
    Sc = (H-h-hb) * W
    ans = min(ans,max([Sa,Sb,Sc])-min([Sa,Sb,Sc]))

for w in range(1,W):
    Sa = H * w
    h = H // 2
    Sb = h * (W-w)
    Sc = (H-h) * (W-w)
    ans = min(ans,max([Sa,Sb,Sc])-min([Sa,Sb,Sc]))

for w in range(1,W):
    Sa = w * H
    wb = (W-w) // 2
    Sb = wb * H
    Sc = (W-w-wb) * H
    ans = min(ans,max([Sa,Sb,Sc])-min([Sa,Sb,Sc]))

print(ans)

Submission status: Accepted

Solution code:
def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

H, W = cin()

def calc(W, H):
    ans = 10 ** 9 + 7
    for h in range(1, H):
        S1 = W * h
        j = H - h
        k = j // 2
        l = j - k
        S2 = W * k
        S3 = W * l
        if S1 and S2 and S3:  ans = min(ans, max(S1, S2, S3) - min(S1, S2, S3))
    for h in range(1, H):
        S1 = h * W
        k = W // 2
        l = W - k
        S2 = (H - h) * k
        S3 = (H - h) * l
        if S1 and S2 and S3:  ans = min(ans, max(S1, S2, S3) - min(S1, S2, S3))
    return ans
ans = calc(W, H)
ans = min(ans, calc(H, W))
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    # 真横に分ける時
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return
    ans = min(W, H)
    # 縦と横に分ける時
    for i in range(1, W):
        s1, s2 = H * i, (W - i) * (H // 2)
        if H % 2 == 0:
            ans = min(ans, abs(s1 - s2))
        else:
            s3 = s2 + W - i
            max_s, min_s = max(s1, s2, s3), min(s1, s2, s3)
            ans = min(ans, max_s - min_s)
    for i in range(1, H):
        s1, s2 = W * i, (H - i) * (W // 2)
        if W % 2 == 0:
            ans = min(ans, abs(s1 - s2))
        else:
            s3 = s2 + H - i
            max_s, min_s = max(s1, s2, s3), min(s1, s2, s3)
            ans = min(ans, max_s - min_s)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W = map(int, input().split())
if H > W:
    H, W = W, H

S = H * W

ans = INF
for i in range(1, H + 1):
    a = i * W
    h = H - i
    w = W
    remain = S - a
    b = h * (w // 2)
    c = remain - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
    b = w * (h // 2)
    c = remain - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
for i in range(1, W + 1):
    a = i * H
    h = H
    w = W - i
    remain = S - a
    b = h * (w // 2)
    c = remain - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
    b = w * (h // 2)
    c = remain - 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())
ans=h*w
for i in range(1,w):
  s1=i*h
  s2=(w-i)//2*h
  s3=w*h-s1-s2
  m1=max(s1,s2,s3)-min(s1,s2,s3)
  s2=h//2*(w-i)
  s3=w*h-s1-s2
  m2=max(s1,s2,s3)-min(s1,s2,s3)
  ans=min(ans,m1,m2)
for i in range(1,h):
  s1=i*w
  s2=(h-i)//2*w
  s3=w*h-s1-s2
  m1=max(s1,s2,s3)-min(s1,s2,s3)
  s2=w//2*(h-i)
  s3=w*h-s1-s2
  m2=max(s1,s2,s3)-min(s1,s2,s3)
  ans=min(ans,m1,m2)
print(ans)

Submission status: Accepted

Solution code:
import sys

def func(h, w):
  ans = sys.maxsize
  h3 = h // 3
  fragments = []
  fragments.append(h3*w)

  if w % 2 == 0:
    fragments.append((h-h3) * w//2)
  else:
    fragments.append((h-h3) * w//2)
    fragments.append((h-h3) * (w//2 + 1))
    
  ans = min(ans, max(fragments) - min(fragments)) 
  
  h3 += 1
  fragments = []
  fragments.append(h3*w)
  if w % 2 == 0:
    fragments.append((h-h3) * w//2)
  else:
    fragments.append((h-h3) * (w//2))
    fragments.append((h-h3) * (w//2 + 1))
    
  ans = min(ans, max(fragments) - min(fragments))
  
  return ans
  

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

# hかwが3で割り切れる場合は0
if h % 3 == 0 or w % 3 == 0:
  print(0)
  sys.exit()

# 縦に2回割る場合はhが差分、横に2回割る場合はwが差分となるので小さい方が正解候補
ans = min(w, h)

# 横1回,縦1回で割る場合
ans = min(func(h,w), func(w,h), ans)

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = 10**9
if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    for width in range(1, w):
        left = width * h
        if h % 2 == 0:
            right_up   = (w-width)*(h//2)
            right_down = right_up
        else:
            right_up   = (w-width)*(h//2+1)
            right_down = (w-width)*(h//2)
        ans = min(ans, max(left, right_up, right_down) - min(left, right_up, right_down))
    for height in range(1, h):
        up = w * height
        if w % 2 == 0:
            down_left  =  (w//2)*(h-height)
            down_right =  down_left
        else:
            down_left  =  (w//2)*(h-height)
            down_right =  (w//2+1)*(h-height)
        ans = min(ans, max(up, down_left, down_right) - min(up, down_left, down_right))
    ans = min(ans, min(h, w))
print(ans)