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:
from math import ceil,floor

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

def S(H,W):
	res = []
	for i in range(1,H):
		S1 = i*W
		S2 = (H-i)*ceil(W/2)
		S3 = (H-i)*floor(W/2)
		S4 = W*ceil((H-i)/2)
		S5 = W*floor((H-i)/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
		res.append(max(S1,S4,S5)-min(S1,S4,S5))
	return(min(res))

print(min(S(H,W),S(W,H)))

Submission status: Accepted

Solution code:
from math import ceil,floor

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

def S(H,W):
	res = []
	for i in range(1,H):
		S1 = i*W
		S2 = (H-i)*ceil(W/2)
		S3 = (H-i)*floor(W/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
	for i in range(1,H):
		S1 = i*W
		S2 = W*ceil((H-i)/2)
		S3 = W*floor((H-i)/2)
		res.append(max(S1,S2,S3)-min(S1,S2,S3))
	return(min(res))

print(min(S(H,W),S(W,H)))

Submission status: Accepted

Solution code:
def solve(h, w):
    res = float('inf')
    for hh in range(h + 1):
        s1 = hh * w
        ww = w // 2
        s2 = (h - hh) * ww
        s3 = (h - hh) * (w - ww)
        res = min(res, max(s1, s2, s3) - min(s1, s2, s3))
    return res


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

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

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
def search(H,W):
    a=H//2
    b=H//2+H%2
    ans=float('inf')
    for w in range(1,W):
        x=a*w
        y=b*w
        z=H*(W-w)
        ans=min(ans,max(x,y,z)-min(x,y,z))
    return ans
if H%3==0 or W%3==0:
    print(0)
else:
    ans=float('inf')
    if H>3:ans=min(ans,W)
    if W>3:ans=min(ans,H)
    print(min(search(H,W),search(W,H),ans))

Submission status: Accepted

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

ans = float('inf')
for i in range(1,w):
    s = []
    s.append(i*h)
    if h%2 == 1:
        s.append((w-i)*(h//2+1))
    s.append((w-i)*(h//2))
    ans = min(ans,max(s)-min(s))

for i in range(1,h):
    s = []
    s.append(i*w)
    if w%2 == 1:
        s.append((h-i)*(w//2+1))
    s.append((h-i)*(w//2))
    ans = min(ans,max(s)-min(s))

ans = min(ans, h*(w//2+1) - h*(w//2), w*(h//2+1) - w*(h//2))
print(ans)

Submission status: Accepted

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



ans = 1e+9
for h in range(1, H):
    # 横と縦で3分割する場合
    S1 = h * W
    S2 = (H - h) * (W // 2)
    S3 = (H - h) * W - S2
    ans = min( ans, max(S1, S2, S3) - min(S1, S2, S3) )
    # 横に3分割する場合
    S2 = (H - h)//2 * W
    S3 = (H - h) * W - S2
    ans = min( ans, max(S1, S2, S3) - min(S1, S2, S3) )

# ひっくり返してもう一回
H, W = W, H 
for h in range(1, H):
    # 横と縦で3分割する場合
    S1 = h * W
    S2 = (H - h) * (W // 2)
    S3 = (H - h) * W - S2
    ans = min( ans, max(S1, S2, S3) - min(S1, S2, S3) )
    # 横に3分割する場合
    S2 = (H - h)//2 * W
    S3 = (H - h) * W - 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())
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = min(H, W)
    for h in range(1, H):
        y = (H - h) * W
        x = h * (W // 2)
        z = h * W - x
        ans = min(ans, max(x, y, z) - min(x, y, z))
    t = H
    H = W
    W = t
    for h in range(1, H):
        y = (H - h) * W
        x = h * (W // 2)
        z = h * W - x
        ans = min(ans, max(x, y, z) - min(x, y, z))
    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 main(a,b):
    ans=99999999999
    for l in range(1,a+1):
        s1=l*b
        s2=(a-l)*(b//2)
        s3=a*b-s1-s2
        s4=((a-l)//2)*b
        s5=a*b-s1-s4
        list1=sorted([s1,s2,s3])
        list2=sorted([s1,s4,s5])
        s=min((list1[-1]-list1[0]),(list2[-1]-list2[0]))
        if ans>s:
            ans=s
    return ans
print(min(main(h,w),main(w,h)))

Submission status: Accepted

Solution code:
def calcdiff(H, W, i):
    a = i * W
    b1 = (H - i) * (W//2)
    c1 = (H - i) * (W - W//2)
    ret = max(a, b1, c1) - min(a, b1, c1)
    b2 = (H - i)//2 * W
    c2 = (H - i - (H - i)//2) * W
    ret = min(ret, max(a, b2, c2) - min(a, b2, c2))
    return ret


def main():
    H, W = map(int, input().split())
    ans = float("inf")
    for i in range(1, H):
        ans = min(ans, calcdiff(H, W, i))
    for i in range(1, W):
        ans = min(ans, calcdiff(W, H, i))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = [H//2+W//3+1, H//3+W//2+1, H, W]
if(H%3 == 0 or W%3 == 0):
  ans += [0]
if(H%2 == 0):
  ans += [H//2]
if(W%2 == 0):
  ans += [W//2]
print(min(ans))

Submission status: Accepted

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

ans = 10**10

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

ans = min(ans,w,h)

for i in range(1,h//2+1):
    a = [w * i, (h - i) * (w // 2), (h - i) * (w // 2 + w % 2)]
    a.sort()
    ans = min(ans, a[2] - a[0])
for i in range(1, w//2+1):
    a = [h * i, (w - i) * (h // 2), (w - i) * (h // 2 + h % 2)]
    a.sort()
    ans = min(ans, a[2] - a[0])
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    print(min(solve(h, w), solve(w, h)))

def solve(h, w):
    m = float('inf')

    for i in range(1, h):
        a = i * w
        m = min(m, divide2(h - i, w, a))
    
    return m

def divide2(h, w, a):
    m = float('inf')
    
    if h >= 2:
        i = h // 2
        b = w * i
        c = w * (h - i)
        m = min(m, max(a, b, c) - min(a, b, c))
    
    if w >= 2:
        i = w // 2
        b = h * i
        c = h * (w - i)
        m = min(m, max(a, b, c) - min(a, b, c))
    
    return m

main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
h,w = LI()
ans = float("inf")
x = w//2
y = h//2
if not w%2:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        ans = min(ans,abs(w*i-x*(h-i)))
else:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        if w*i < x*(h-i):
            ans = min(ans,abs(w*i-(x+1)*(h-i)))
        elif w*i < (x+1)*(h-i):
            ans = min(ans,h-i)
        else:
            ans = min(ans,abs(w*i-x*(h-i)))
if not h%2:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        ans = min(ans,abs(h*i-y*(w-i)))
else:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        if h*i < y*(w-i):
            ans = min(ans,abs(h*i-(y+1)*(w-i)))
        elif h*i < (y+1)*(w-i):
            ans = min(ans,w-i)
        else:
            ans = min(ans,abs(h*i-y*(w-i)))
print(ans)

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

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

ans = min(h, w)

a = [0,0,0]
for i in range(2):
    b = h // 3 + i
    a[0] = b * w
    a[1] = (h - b) * (w // 2)
    a[2] = (h - b) * (w - (w // 2))

    ans = min(ans, max(a) - min(a))

for i in range(2):
    b = w // 3 + i
    a[0] = b * h
    a[1] = (w - b) * (h // 2)
    a[2] = (w - b) * (h - (h // 2))

    ans = min(ans, max(a) - min(a))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = float('inf')
for i in range(1, H):
    a = i * W
    b = ((H - i) // 2) * W
    c = ((H - i) - (H - i) // 2) * W
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, H):
    a = i * W
    b = (H - i) * (W // 2)
    c = (H - i) * (W - W // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, W):
    a = i * H
    b = (H // 2) * (W - i)
    c = (H - H // 2) * (W - i)
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)
    
for i in range(1, W):
    a = i * H
    b = ((W - i) // 2) * H
    c = ((W - i) - (W - i) // 2) * H
    tmp = max(a, b, c) - min(a, b, c)
    ans = min(ans, tmp)    
    
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    # pattern1は縦or横にぶった切るパターン
    pattern1 = min(w, h)
    # pattern2は縦と横に切るパターン(pattern2にも2パターンある)
    # (a, b)のセットと, cのブロックで考える
    a_w = w // 2
    b_w = w - a_w
    c_w = w
    pattern2_1 = float("inf")
    for tmp_h in range(1, h + 1):
        tmp_diff = max(abs(c_w * tmp_h - a_w * (h - tmp_h)), abs(c_w * tmp_h - b_w * (h - tmp_h)))
        if tmp_diff < pattern2_1:
            pattern2_1 = tmp_diff
        else:
            break
    a_h = h // 2
    b_h = h - a_h
    c_h = h
    pattern2_2 = float("inf")
    for tmp_w in range(1, w + 1):
        tmp_diff = max(abs(c_h * tmp_w - a_h * (w - tmp_w)), abs(c_h * tmp_w - b_h * (w - tmp_w)))
        if tmp_diff < pattern2_2:
            pattern2_2 = tmp_diff
        else:
            break
    print(min(pattern1, pattern2_1, pattern2_2))

Submission status: Accepted

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

inf = float("inf")
ans = inf

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

case1 = [(H//3)  * W, (H-(H//3))*(W//2), (H-(H//3))*(W-W//2)]
case2 = [(H//3 + 1)  * W, (H-(H//3)-1)*(W//2), (H-(H//3)-1)*(W-W//2)]

case3 = [(W//3)  * H, (W-(W//3))*(H//2), (W-W//3) * (H-H//2)]
case4 = [(W//3 + 1)  * H, (W-(W//3)-1)*(H//2), (W-W//3 - 1) * (H-H//2)]

case5 = [H//3 * W, (H-H//3)//2 * W, (H- H//3 - (H-H//3)//2) * W] 
case6 = [W//3 * H, (W-W//3)//2 * H, (W- W//3 - (W-W//3)//2) * H] 

ans = min(ans,  max(case1) - min(case1))
ans = min(ans,  max(case2) - min(case2))
ans = min(ans,  max(case3) - min(case3))
ans = min(ans,  max(case4) - min(case4))
ans = min(ans,  max(case5) - min(case5))
ans = min(ans,  max(case6) - min(case6))

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)
else:
    res = 10 ** 11
    for i in range(1, H):
        a = W*i
        b = math.ceil(W/2) * (H-i)
        m = W//2 * (H-i)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, W):
        a = H*i
        b = math.ceil(H/2) * (W-i)
        m = H//2 * (W-i)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, H-1):
        a = W*i
        b = W * math.ceil((H-i)/2)
        m = W * ((H-i)//2)
        res = min(res, max(a,b,m)-min(a,b,m))

    for i in range(1, W-1):
        a = H*i
        b = H * math.ceil((W-i)/2)
        m = H * ((W-i)//2)
        res = min(res, max(a,b,m)-min(a,b,m))

               
    print(res)

Submission status: Accepted

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

if h%3==0:
  print(0)
elif h%3==0:
  print(0)
elif h%2==0 and w%2==0:
  ans=min(w,h)
  for i in range(w+1):
    ans = min(abs((h//2)*(w-i)-h*i),ans)
  for i in range(h+1):
    ans = min(abs((w//2)*(h-i)-w*i),ans)
  print(ans)
elif h%2==0 and w%2==1:
  ans=min(w,h)
  for i in range(w+1):
    ans = min(abs((h//2)*(w-i)-h*i),ans)
  for i in range(h+1):
    ans = min(max(abs((w//2)*(h-i)-w*i),abs((w//2+1)*(h-i)-w*i),abs(h-i)),ans)
  print(ans)
elif h%2==1 and w%2==0:
  ans=min(w,h)
  h,w=w,h
  for i in range(w+1):
    ans = min(abs((h//2)*(w-i)-h*i),ans)
  for i in range(h+1):
    ans = min(max(abs((w//2)*(h-i)-w*i),abs((w//2+1)*(h-i)-w*i),abs(h-i)),ans)
  print(ans)
elif h%2==1 and w%2==1:
  ans=min(w,h)
  for i in range(w+1):
    ans = min(max(abs((h//2)*(w-i)-h*i),abs((h//2+1)*(w-i)-h*i),abs(w-i)),ans)
  for i in range(h+1):
    ans = min(max(abs((w//2)*(h-i)-w*i),abs((w//2+1)*(h-i)-w*i),abs(h-i)),ans)
  print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
def solve(h, w):
    res = 10 ** 9
    for i in range(1, h):
        s1 = i * w
        h1 = h - i
        w1 = w // 2
        w2 = w - w //2
        s2 = h1 * w1
        s3 = h1 * w2
        diff = max([s1, s2, s3]) - min([s1, s2, s3])
        if res > diff:
            res = diff
        h2 = h1 // 2
        h3 = h1 - h1 // 2
        s2 = h2 * w
        s3 = h3 * w
        diff = max([s1, s2, s3]) - min([s1, s2, s3])
        if res > diff:
            res = diff
    return res
print(min(solve(H, W), solve(W, H)))

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
ans = min(H, W)
h = round(H / 3)
w = W // 2
a = h * W
b = (H-h) * w
c = (H-h) * (W-w)
ans = min(ans, max(a, b, c) - min(a, b, c))

h = H // 2
w = round(W / 3)
a = H * w
b = (W-w) * h
c = (W-w) * (H-h)
ans = min(ans, max(a, b, c) - min(a, b, c))
if(H%3 == 0 or W%3 == 0):
  ans = 0
print(ans)

Submission status: Accepted

Solution code:
def f(h, w):
    l = []
    for i in range(w):
        m = [(w-i)*h, i*(h//2), i*(h-h//2)]
        l.append(max(m)-min(m))
    # print(l)
    return min(l)

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

if 0 in [H%3, W%3]:
    print(0)
else:
    # T字分割縦, T字分割横、3列分割縦、3列分割横
    print(min(f(H, W), f(W, H), H, W))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

from collections import defaultdict, Counter
from math import pi, sqrt
from bisect import bisect_left, bisect_right

def req_S(h, w):
    tmp_s = []
    a_w = w
    for a_h in range(1, h):
        # b, cが横のパターン
        b_h = (h-a_h)//2
        c_h = h-b_h-a_h
        b_w, c_w = w, w
        S = [a_w*a_h, b_w*b_h, c_w*c_h]
        tmp_s.append(max(S)-min(S))
        # b, cが縦のパターン
        b_w = w//2
        c_w = w-b_w
        b_h, c_h = h-a_h, h-a_h
        S = [a_w*a_h, b_w*b_h, c_w*c_h]
        tmp_s.append(max(S)-min(S))
    return tmp_s

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

all_S = req_S(h, w) + req_S(w, h)
print(min(all_S))

Submission status: Accepted

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

def calc(H,W,ans):
    for i in range(1,H):
        Sa = i * W
        h = (H-i) // 2
        Sb = h * W
        Sc = (H-i-h) * W
        d1 = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
        w = W // 2
        Sb = (H-i) * w
        Sc = (H-i) * (W-w)
        d2 = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
        if ans > min(d1,d2): ans = min(d1,d2)
    return ans

ans = 1000000
ans = calc(H,W,ans)
ans = calc(W,H,ans)

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = float("inf")
for i in range(h):
    choco = [i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(w):
    choco = [i * h, (w - i) * (h // 2), (w - i) * (h - h // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(h):
    choco = [i * w, w * ((h - i) // 2), w * ((h - i) - (h - i) // 2)]
    ans = min(ans, max(choco) - min(choco))
for i in range(w):
    choco = [i * h, h * ((w - i) // 2), h * ((w - i) - (w - i) // 2)]
    ans = min(ans, max(choco) - min(choco))
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 = float("inf")
    for i in range(h):
        choco = [i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(w):
        choco = [i * h, (w - i) * (h // 2), (w - i) * (h - h // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(h):
        choco = [i * w, w * ((h - i) // 2), w * ((h - i) - (h - i) // 2)]
        ans = min(ans, max(choco) - min(choco))
    for i in range(w):
        choco = [i * h, h * ((w - i) // 2), h * ((w - i) - (w - i) // 2)]
        ans = min(ans, max(choco) - min(choco))
    print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=10**9
w1,w2=w//2,w-w//2
for i in range(1,h):
  s=i*w,w1*(h-i),w2*(h-i)
  ans=min(ans,max(s)-min(s))
h1,h2=h//2,h-h//2
for i in range(1,w):
  s=i*h,h1*(w-i),h2*(w-i)
  ans=min(ans,max(s)-min(s))
if h%3==0 or w%3==0:
  ans=0
if w >2:
  ans=min(ans,w)
if h >2:
  ans=min(ans,h)
print(ans)

Submission status: Accepted

Solution code:
def choco(h, w):

    ans = [(h % 3 != 0) * w,
           (h - (h // 3)) * (w // 2 + (w % 2 != 0)) - min( (h // 3) * w, (h - (h // 3)) * (w // 2) ),
           (h // 3  + 1) * w - (h - (h // 3 + 1)) * (w // 2)]
    return(min(ans))
    
h, w = [int(i) for i in input().split()]   
print(min(choco(h, w), choco(w, h)))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def ceil(x):
    return int((-x)//(1)*(-1))


def solve(a, b):
    """
    a,b = H,W or W,H
    aの方を三等分ぽく分解する
    """
    upper = ceil(a/3)
    lower = a//3
    l = [0]*3
    ret = float('inf')
    for i in range(lower, upper+1):
        if b % 2 == 0:
            l[0] = i*b
            l[1] = (a-i)*b//2
            l[2] = (a-i)*b//2
        else:
            l[0] = i*b
            l[1] = (a-i)*(b//2)
            l[2] = (a-i)*(b//2+1)
        ret = min(max(l)-min(l), ret, b)
    return ret


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:
H ,W = map(int,input().split())
S = H*W
def ceil(i):
    if int(i) != i:
        return int(i)+1
    else:
        return int(i)

harfH1 = int(H/2)
harfH2 = ceil(H/2)
harfW1 = int(W/2)
harfW2 = ceil(W/2)
ans = 1000000000
for i in range(1,W):
    S1 = i*H
    S2 = (W-i) * harfH1 
    S3 = (W-i) * harfH2 
    diff = max(S1,S2,S3) - min(S1,S2,S3)
    ans = min(ans,diff)
for i in range(1,H):
    S1 = W*i
    S2 = harfW1 * (H-i)
    S3 = harfW2 * (H-i)
    diff = max(S1,S2,S3) - min(S1,S2,S3)
    ans = min(ans,diff)
if H % 3 == 0 or W % 3 == 0:
    ans = 0
else:
    ans = min(ans,W,H)
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
minAns = float('inf')
for h in range(1,H+1):
    hh = -(-(H-h)//2)
    hd = -(-W//2)
    A = h*W
    B = hh*W
    C = (H-h-hh)*W
    D = hd*(H-h)
    E = (W-hd)*(H-h)
    M1 = max(A,B,C)
    m1 = min(A,B,C)
    M2 = max(A,D,E)
    m2 = min(A,D,E)
    minAns = min(minAns,M1-m1,M2-m2)
H,W = W,H
for h in range(1,H+1):
    hh = -(-(H-h)//2)
    hd = -(-W//2)
    A = h*W
    B = hh*W
    C = (H-h-hh)*W
    D = hd*(H-h)
    E = (W-hd)*(H-h)
    M1 = max(A,B,C)
    m1 = min(A,B,C)
    M2 = max(A,D,E)
    m2 = min(A,D,E)
    minAns = min(minAns,M1-m1,M2-m2)
print(minAns)

Submission status: Accepted

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

for h in range(1,H):
    l = H-h
    cand1 = [h*W]
    cand2 = [h*W]
    cand1.append(l//2*W)
    cand1.append((l-l//2)*W)
    cand2.append(l*(W//2))
    cand2.append(l*(W-W//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))

for w in range(1,W):
    l = W-w
    cand1 = [H*w]
    cand2 = [H*w]
    cand1.append(H*(l//2))
    cand1.append(H*(l-l//2))
    cand2.append(l*(H//2))
    cand2.append(l*(H-H//2))
    candidate.append(max(cand1)-min(cand1))
    candidate.append(max(cand2)-min(cand2))
    
        

print(min(candidate))

Submission status: Accepted

Solution code:
def yoko3(x, w, h):
    s1 = x * w
    h2 = (h-x)//2
    s2 = h2 * w
    s3 = (h - h2 - x) * w

    s = {s1, s2, s3}

    return max(s) - min(s)


def yoko1tate2(x, w, h):
    s1 = x * w
    w2 = w // 2
    s2 = (h-x)*w2
    s3 = (h-x)*(w-w2)

    s = {s1, s2, s3}

    return max(s) - min(s)


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

    ans = float("inf")
    ans = min(ans, min([yoko3(x, W, H) for x in range(H)]))
    ans = min(ans, min([yoko3(x, H, W) for x in range(W)]))
    ans = min(ans, min([yoko1tate2(x, W, H) for x in range(H)]))
    ans = min(ans, min([yoko1tate2(x, H, W) for x in range(W)]))

    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

def divide(H, W):
    if (H*W)%2 == 0:
        return H*W//2, H*W//2
    else:
        if H > W:
            return W*(H-1)//2, W*(H+1)//2
        else:
            return H*(W-1)//2, H*(W+1)//2

minval = 10000000000
for i in range(1, H):
    S0 = W*i
    S1, S2 = divide(H-i, W)
    minval = min(minval, max(abs(S0-S1), abs(S1-S2), abs(S2-S0)))
for i in range(1, W):
    S0 = H*i
    S1, S2 = divide(H, W-i)
    minval = min(minval, max(abs(S0-S1), abs(S1-S2), abs(S2-S0)))
print(minval)

Submission status: Accepted

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

ans1 = h * w
for i in range(1, h + 1):
    a = i * w
    b = (h - i) * (w // 2)
    c = (h - i) * (w - w // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans1 = min(ans1, tmp)
    
ans2 = h * w
for i in range(1, w + 1):
    a = i * h
    b = (w - i) * (h // 2)
    c = (w - i) * (h - h // 2)
    tmp = max(a, b, c) - min(a, b, c)
    ans2 = min(ans2, tmp)
    
ans3 = h * w
for i in range(1, h + 1):
    a = i * w
    b = (h - i) // 2 * w
    c = (h - i - (h - i) // 2) * w
    tmp = max(a, b, c) - min(a, b, c)
    ans3 = min(ans3, tmp)
    
    
ans4 = h * w
for i in range(1, h + 1):
    a = i * h
    b = (w - i) // 2 * h
    c = (w - i - (w - i) // 2) * h
    tmp = max(a, b, c) - min(a, b, c)
    ans4 = min(ans4, tmp)    
    
print(min(ans1, ans2, ans3, ans4))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s, l = min(H, W), max(H, W)

ans = 10**6
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    for i in range(1, l):
        area1 = s*i
        area2 = s//2 * (l - i)
        area3 = area2 if s % 2 == 0 else (s//2 + 1) * (l - i)
        ans = min(ans, max(area1, area2, area3) - min(area1, area2, area3))
    for i in range(1, s):
        area1 = l*i
        area2 = l//2 * (s - i)
        area3 = area2 if l % 2 == 0 else (l//2 + 1) * (s - i)
        ans = min(ans, max(area1, area2, area3) - min(area1, area2, area3))
    ans = min(ans, H, W)
    print(ans)

Submission status: Accepted

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

if h * w % 3 == 0:
    ans = 0
    
else:
    ans1 = 10 ** 5
    for i in range(1, h + 1):
        a = i * w
        b = (h - i) * (w // 2)
        c = (h - i ) * (w - w // 2)
        tmp = max(a, b, c) - min(a, b, c)
        ans1 = min(ans1, tmp)
        
    ans2 = 10 ** 5
    for i in range(1, w + 1):
        a = i * h
        b = (w- i) * (h // 2)
        c = (w - i) * (h - h // 2)
        tmp = max(a, b, c) - min(a, b, c)
        ans2 = min(ans2, tmp)
        
    ans3 = 10 ** 5
    for i in range(1, h + 1):
        a = i * w
        b = (h - i) // 2 * w
        c = (h - i - (h - i) // 2) * w
        tmp = max(a, b, c) - min(a, b, c)
        ans3 = min(ans3, tmp)
        
    ans4 = 10 ** 5
    for i in range(1, w + 1):
        a = i * h
        b = (w - i) // 2 * h
        c = (w - i - (w - i) // 2) * h
        tmp = max(a, b, c) - min(a, b, c)
        ans4 = min(ans4, tmp)
        
    ans = min(ans1, ans2, ans3, ans4)
    
print(ans)

Submission status: Accepted

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

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

ans = min(W, H)
for i in range(1, H):
    tmp1 = W//2*(H-i)
    tmp2 = tmp1 if W % 2 == 0 else tmp1+H-i
    tmp3 = i*W
    ans = min(ans, max(abs(tmp1-tmp2), abs(tmp2-tmp3), abs(tmp3-tmp1)))
for i in range(1, W):
    tmp1 = H//2*(W-i)
    tmp2 = tmp1 if H % 2 == 0 else tmp1+W-i
    tmp3 = i*H
    ans = min(ans, max(abs(tmp1-tmp2), abs(tmp2-tmp3), abs(tmp3-tmp1)))
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
s = H*W
def func(h,w):
    tmp = float("inf")
    for x in range(1,w):
        s1 = h*x
        s2 = (w-x)*(h//2)
        s3 = s - s1 - s2
        d = max(s1,s2,s3) - min(s1,s2,s3)
        if d < tmp:
            tmp = d
    return tmp
ans = min(func(H,W),func(W,H),min(W%3,1)*H,(min(H%3,1)*W))
print(ans)

Submission status: Accepted

Solution code:
h,w = (int(i) for i in input().split())
ans = 99999999999999999
for i in range(0,h):
  sa = i*w
  #上下分断
  h2 = (h-i)//2
  sb = h2*w
  sc = (h-i-h2)*w
  judgema = max([sa,sb,sc])
  judgemi = min([sa,sb,sc])
  ans = min(ans,(judgema-judgemi))
  #左右分断
  w2 = (w//2)
  sb = (h-i)*w2
  sc = (h-i)*(w-w2)
  judgema = max([sa,sb,sc])
  judgemi = min([sa,sb,sc])
  ans = min(ans,(judgema-judgemi))

tmp1 = h
tmp2 = w
w =tmp1
h =tmp2
for i in range(0,h):
  sa = i*w
  #上下分断
  h2 = (h-i)//2
  sb = h2*w
  sc = (h-i-h2)*w
  judgema = max([sa,sb,sc])
  judgemi = min([sa,sb,sc])
  ans = min(ans,(judgema-judgemi))
  #左右分断
  w2 = (w//2)
  sb = (h-i)*w2
  sc = (h-i)*(w-w2)
  judgema = max([sa,sb,sc])
  judgemi = min([sa,sb,sc])
  ans = min(ans,(judgema-judgemi))
  
print(ans)

Submission status: Accepted

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

ans = 9999999999
# 高さの分割で全探索
for h in range(1,H):
    s1 = h*W
    # 残った領域をさらに高さで分割
    s2 = ((H-h)//2)*W 
    s3 = (H-h-(H-h)//2)*W
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    # 残った領域を幅で分割
    s2 = (W//2)*(H-h)
    s3 = (W-W//2)*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))


# 高さと幅を入れ替えて再実行
H,W = W,H
for h in range(1,H):
    s1 = h*W
    # 残った領域をさらに高さで分割
    s2 = ((H-h)//2)*W 
    s3 = (H-h-(H-h)//2)*W
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    # 残った領域を幅で分割
    s2 = (W//2)*(H-h)
    s3 = (W-W//2)*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))

print(ans)

Submission status: Accepted

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

if 0 in [H % 3, W % 3]:
    print(0)
    exit()


def calc(x, y):
    res = float('inf')
    for p in [y // 3, 1 + y // 3]:
        q = x // 2
        a = sorted([x * p, q * (y - p), (x - q) * (y - p)])
        res = min(res, abs(a[2] - a[0]))
    return res


print(min(H, W, calc(H, W), calc(W, H)))

Submission status: Accepted

Solution code:
import math

def tcut(H,W):
    arr1 = [math.floor(2*H/3),math.ceil(2*H/3)]
    arr2 = [math.floor(W/2),math.ceil(W/2)]
    minS = H*W
    for h in arr1:
        for w in arr2:
            smax = max(h*w,(H-h)*W,h*(W-w))
            smin = min(h*w,(H-h)*W,h*(W-w))
            if minS > smax - smin:
                minS = smax - smin
    return minS

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

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    Tcut = min(tcut(H,W),tcut(W,H))
    stcut = min(H,W)
    print(min(Tcut,stcut))

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
else:
    cand = []
    for i in range(1, H):
        # 横に分割
        S1 = i * W
        S2 = (H - i) * (W // 2)
        S3 = (H - i) * (W - W // 2)
        cand.append(max(S1, S2, S3) - min(S1, S2, S3))
        # 縦に分割
        S2 = (H - i) // 2 * W
        S3 = ((H - i) - (H - i) // 2) * W
        cand.append(max(S1, S2, S3) - min(S1, S2, S3))
    for i in range(1, W):
        # 横に分割
        S1 = i * H
        S2 = (W - i) * (H // 2)
        S3 = (W - i) * (H - H // 2)
        cand.append(max(S1, S2, S3) - min(S1, S2, S3))
        # 縦に分割
        S2 = (W - i) // 2 * H
        S3 = ((W - i) - (W - i) // 2) * H
        cand.append(max(S1, S2, S3) - min(S1, S2, S3))
    print(min(cand))

Submission status: Accepted

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

result = []
for h in range(1, H//2+1):
    Sa = W * h

    remain = H - h
    h2 = (remain + 1) // 2
    Sb1 = W * h2
    Sc1 = W * (remain - h2)
    result.append(max(Sa, Sb1, Sc1) - min(Sa, Sb1, Sc1))

    w = (W + 1) // 2
    Sb2 = w * remain
    Sc2 = (W - w) * remain
    result.append(max(Sa, Sb2, Sc2) - min(Sa, Sb2, Sc2))

for w in range(1, W//2+1):
    Sa = H * w

    remain = W - w
    w3 = (remain + 1) // 2
    Sb1 = H * w3
    Sc1 = H * (remain - w3)
    result.append(max(Sa, Sb1, Sc1) - min(Sa, Sb1, Sc1))

    h = (H + 1) // 2
    Sb2 = h * remain
    Sc2 = (H - h) * remain
    result.append(max(Sa, Sb2, Sc2) - min(Sa, Sb2, Sc2))

print(min(result))

Submission status: Accepted

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

result = []
for h in range(1, H):
    Sa = W * h

    remain = H - h
    h2 = (remain + 1) // 2
    Sb1 = W * h2
    Sc1 = W * (remain - h2)
    result.append(max(Sa, Sb1, Sc1) - min(Sa, Sb1, Sc1))

    w = (W + 1) // 2
    Sb2 = w * remain
    Sc2 = (W - w) * remain
    result.append(max(Sa, Sb2, Sc2) - min(Sa, Sb2, Sc2))

for w in range(1, W):
    Sa = H * w

    remain = W - w
    w3 = (remain + 1) // 2
    Sb1 = H * w3
    Sc1 = H * (remain - w3)
    result.append(max(Sa, Sb1, Sc1) - min(Sa, Sb1, Sc1))

    h = (H + 1) // 2
    Sb2 = h * remain
    Sc2 = (H - h) * remain
    result.append(max(Sa, Sb2, Sc2) - min(Sa, Sb2, Sc2))

print(min(result))