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:
import bisect
H,W = map(int,input().split())
ans = H*W
for h in range(H):
    h1 = (H-h)//2 if (H-h)%2==0 else (H-h)//2+1
    Smax = max(h*W, h1*W)
    Smin = min(h*W, ((H-h)//2)*W)
    ans = min(ans, Smax-Smin)
    w1 = W//2 if W%2==0 else W//2+1
    Smax = max(h*W, (H-h)*w1)
    Smin = min(h*W, (H-h)*(W//2))
    ans = min(ans, Smax-Smin)
for w in range(W):
    w1 = (W-w)//2 if (W-w)%2==0 else (W-w)//2+1
    Smax = max(H*w, H*w1)
    Smin = min(H*w, H*((W-w)//2))
    ans = min(ans, Smax-Smin)
    h1 = H//2 if H%2==0 else H//2+1
    Smax = max(H*w, h1*(W-w))
    Smin = min(H*w, (H//2)*(W-w))
    ans = min(ans, Smax-Smin)
print(ans)

Submission status: Accepted

Solution code:
# 2019/09/03

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

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


def solve(s):
    global h,w
    
    cnt=float('inf')
    if s==h:
        H,W=w,h
    else:
        H,W=h,w
    for i in range(1,s+1):
        a=i*H
        rest=H*(w-i)
        if rest%2==0:
            b=c=rest//2
        else:
            ww=W-i
            hh=H
            bb=max(ww,hh)//2
            cc=bb+1
            b=min(ww,hh)*bb
            c=min(ww,hh)*cc
        cnt=min((max(a,b,c)-min(a,b,c)),cnt)

    return cnt


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

Submission status: Accepted

Solution code:
h,w=map(int,input().split());print(min(h//2+w//3+1,h//3+w//2+1,h*(h%3>0)//(2-h%2),w*(w%3>0)//(2-w%2)))

Submission status: Accepted

Solution code:
def f(x,y):
	m=x*(x%3>0)
	for i in range(2):
		d=x//3+i;e=x-d;l=sorted([d*y,e*(y//2),e*(-~y//2)]);m=min(m,l[2]-l[0])
	return m
h,w=map(int,input().split())
print(min(f(h,w),f(w,h)))

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    if min(h % 3, w % 3) == 0:
        print(0)
        return
    # if [h, w] == [2, 2]:
    #     print(1)
    #     return
    s = h * w
    ans = min(h, w)
    for wcut in range(1, w // 2 + 1):
        s1 = wcut * h
        s2 = (w - wcut) * (h // 2)
        s3 = s - s1 - s2
        ans = min(ans, max(s1, s3) - min(s1, s2))
    for hcut in range(1, h // 2 + 1):
        s1 = hcut * w
        s2 = (h - hcut) * (w // 2)
        s3 = s - s1 - s2
        ans = min(ans, max(s1, s3) - min(s1, s2))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = min(H,W)
for h in range(H//3,H//3+3):
    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//3+3):
    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))

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

Submission status: Accepted

Solution code:
li = [int(x) for x in input().split()]
H,W = max(li),min(li)
ans = float('inf')
if(H%3==0 or W%3==0):
    ans = 0
else:
    ans = W

S0 = [0]*3

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

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

print(ans)

Submission status: Accepted

Solution code:
import math
c, f = math.ceil, math.floor

def diff(arr):
    return max(arr) - min(arr)


def solve(h, w):
    if h%3 == 0 or w%3 == 0:
        return 0

    ps = [
        [h*c(w/3), c(h/2)*(w-c(w/3)), (h-c(h/2))*(w-c(w/3))],
        [h*c(w/3), f(h/2)*(w-c(w/3)), (h-f(h/2))*(w-c(w/3))],
        [h*f(w/3), c(h/2)*(w-f(w/3)), (h-c(h/2))*(w-f(w/3))],
        [h*f(w/3), f(h/2)*(w-f(w/3)), (h-f(h/2))*(w-f(w/3))],
        [w*c(h/3), c(w/2)*(h-c(h/3)), (w-c(w/2))*(h-c(h/3))],
        [w*c(h/3), f(w/2)*(h-c(h/3)), (w-f(w/2))*(h-c(h/3))],
        [w*f(h/3), c(w/2)*(h-f(h/3)), (w-c(w/2))*(h-f(h/3))],
        [w*f(h/3), f(w/2)*(h-f(h/3)), (w-f(w/2))*(h-f(h/3))],
        [h*c(w/3), h*c(w/3), h*(w-2*c(w/3))],
        [h*c(w/3), h*f(w/3), h*(w-c(w/3)-f(w/3))],
        [h*f(w/3), h*f(w/3), h*(w-2*f(w/3))],
        [w*c(h/3), w*c(h/3), w*(h-2*c(h/3))],
        [w*c(h/3), w*f(h/3), w*(h-c(h/3)-f(h/3))],
        [w*f(h/3), w*f(h/3), w*(h-2*f(h/3))],
    ]
    values = [diff(p) for p in ps]
    return min(values)

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

"""
"""

Submission status: Accepted

Solution code:
H, W = map(int ,input().split())
ans = []
for i in range(1,H):
    a = W * i
    if W % 2 == 0:
        b = W//2 * (H-i)
        c = W//2 * (H-i)
    else:
        b = W//2 * (H-i)
        c = (W+1)//2 * (H-i)
    maxtmp = max(a, b, c)
    mintmp = min(a, b, c)
    tmp = maxtmp - mintmp
    ans.append(tmp)

for i in range(1,W):
    a = H * i
    if H % 2 == 0:
        b = H//2 * (W-i)
        c = H//2 * (W-i)
    else:
        b = H//2 * (W-i)
        c = (H+1)//2 * (W-i)
    maxtmp = max(a, b, c)
    mintmp = min(a, b, c)
    tmp = maxtmp - mintmp
    ans.append(tmp)

if W % 3 == 0:
    ans.append(0)
else:
    ans.append(H) 

if H % 3 == 0:
    ans.append(0)
else:
    ans.append(W)

ans = min(ans)
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(W, H)
    for a1 in [W // 3, -(-W // 3)] :
        for a2 in [H // 2, -(-H // 2)] :
            A1 = a1 * H
            A2 = a2 * (W - a1)
            A3 = H * W - A1 - A2
            ans = min(ans, max(A1, A2, A3) - min(A1, A2, A3))
    for a1 in [H // 3, -(-H // 3)] :
        for a2 in [W // 2, -(-W // 2)] :
            A1 = a1 * W
            A2 = a2 * (H - a1)
            A3 = H * W - A1 - A2
            ans = min(ans, max(A1, A2, A3) - min(A1, A2, A3))
    print(ans)

Submission status: Accepted

Solution code:
# ARC074C - Chocolate Bar (ABC062C)
from itertools import accumulate


def divide_bar(A: int, B: int) -> int:
    # x: one of partial rectangles
    # y: another one -> (y1, y2), (y2, y3): divide to updown, left-right
    ret = set()
    area = A * B
    for i, x in enumerate(accumulate([A] * (B // 2)), 1):
        y = area - x
        y1 = y * (A // 2) // A
        y2 = y - y1
        y3 = y * ((B - i) // 2) // (B - i)
        y4 = y - y3
        ret |= {max(x, y1, y2) - min(x, y1, y2)}
        ret |= {max(x, y3, y4) - min(x, y3, y4)}
    return min(ret)


def main():
    H, W = tuple(map(int, input().rstrip().split()))
    ans = min(divide_bar(H, W), divide_bar(W, H))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    ans = 10**12
    s = h * w
    for p in [h//3, h//3 + 1]:
        s1 = w * p
        s2 = (w // 2) * (h - p)
        s3 = (w - (w // 2)) * (h - p)
        ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    for p in [w//3, w//3 + 1]:
        s1 = h * p
        s2 = (h // 2) * (w - p)
        s3 = (h - (h // 2)) * (w - p)
        ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    s1 = w * (h//3)
    s2 = w * (h//3+1)
    ans = min(ans,(max(s1,s2)-min(s1,s2)))
    s1 = h * (w//3)
    s2 = h * (w//3+1)
    ans = min(ans,(max(s1,s2)-min(s1,s2)))
    
print(ans)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())

def f(H, W):
    tmp = 100000000000
    for h in range(1, H):
        s = []
        s.append(h * W)
        s.append((H - h) // 2 * W)
        s.append((((H - h) // 2) + (H - h) % 2) * W)
        s.sort()
        tmp = min(tmp, s[2] - s[0])
        s = []
        s.append(h * W)
        s.append(W // 2 * (H - h))
        s.append((W // 2 + W % 2) * (H - h))
        s.sort()
        tmp = min(tmp, s[2] - s[0])
    return tmp

ans = min(f(a, b), f(b, a))

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a=[[(H//3)*W,((H-1)//3+1)*W],[H*(W//3),((W-1)//3+1)*H],
[(H//3)*W,(H-H//3)*(W//2),(H-H//3)*(W-W//2)],
[(W//3)*H,(W-W//3)*(H//2),(W-W//3)*(H-H//2)],
[((H-1)//3+1)*W,(H-((H-1)//3+1))*(W//2),(H-((H-1)//3+1))*(W-W//2)],
[((W-1)//3+1)*H,(W-((W-1)//3+1))*(H//2),(W-((W-1)//3+1))*(H-H//2)]]
print(min([max(e)-min(e) for e in a]))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    temp=[]
    #1
    h1=h//3
    w1=w
    temp.append([h1*w1,((h-h1)//2)*w,((h-h1+1)//2)*w])
    temp.append([h1*w1,(h-h1)*(w//2),(h-h1)*((w+1)//2)])
    #2
    h1=(h+2)//3
    w1=w
    temp.append([h1*w1,((h-h1)//2)*w,((h-h1+1)//2)*w])
    temp.append([h1*w1,(h-h1)*(w//2),(h-h1)*((w+1)//2)])
    #3
    h,w=w,h
    h1=h//3
    w1=w
    temp.append([h1*w1,((h-h1)//2)*w,((h-h1+1)//2)*w])
    temp.append([h1*w1,(h-h1)*(w//2),(h-h1)*((w+1)//2)])
    #4
    h1=(h+2)//3
    w1=w
    temp.append([h1*w1,((h-h1)//2)*w,((h-h1+1)//2)*w])
    temp.append([h1*w1,(h-h1)*(w//2),(h-h1)*((w+1)//2)])
    
    print(min([max(t)-min(t) for t in temp]))

Submission status: Accepted

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

min_d=10**27

if H%3==0 or W%3==0:
    print(0)
else:
    min_d=min(H,W)
    for i in range(H+1):
        a=i*W
        b=(H-i)*(W//2)
        c=(H-i)*W - b
        min_d = min(max(a,b,c)-min(a,b,c),min_d)
    for i in range(W+1):
        a=i*H
        b=(W-i)*(H//2)
        c=(W-i)*H - b
        min_d = min(max(a,b,c)-min(a,b,c),min_d)
    print(min_d)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
h,w = [int(i) for i in input().split()]

def once(h,w):
    res = 10**9
    if h > 1:
        a,b = h//2*w, (h-h//2)*w
        res = abs(a-b)
    if w > 1:
        c,d = w//2*h, (w-w//2)*h
        if abs(c-d) < res:
            a,b = c,d
    return a,b    


def hsaki(h,w):
    res = 10**9
    for i in range(1,h):
        p1 = i*w
        p2,p3 = once(h-i,w)
        a = max(p1,p2,p3) - min(p1,p2,p3) 
        res = min(res, a)
#        print(p1,p2,p3)
    return res

#print(hsaki(h,w), hsaki(w,h))

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0: print(0)
else:
    total = H*W
    ans = 10**10
    for i in range(1, H):
        S1 = W*i
        S2a = W*((H-i)//2); S3a = total - (S1 + S2a);
        S2b = (W//2)*(H-i); S3b = total - (S1 + S2b);
        ans = min(ans, min(max(S1, S2a, S3a) - min(S1, S2a, S3a), max(S1, S2b, S3b) - min(S1, S2b, S3b)))
    for i in range(1, W):
        S1 = H*i
        S2a = H*((W-i)//2); S3a = total - (S1 + S2a);
        S2b = (H//2)*(W-i); S3b = total - (S1 + S2b);
        ans = min(ans, min(max(S1, S2a, S3a) - min(S1, S2a, S3a), max(S1, S2b, S3b) - min(S1, S2b, S3b)))
    print(ans)

Submission status: Accepted

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


def diff(L):
    return(max(L)-min(L))

def solve(H: int, W: int):
    N = 3
    if H % N == 0 or W % N == 0:
        print(0)
        return
    
    res = H * W
    for h in range(1, H):
        s1 = (H - h) * W

        s2 = h * (W // 2)
        s3 = h * (W - W // 2)
        res = min(res, diff([s1, s2, s3]))

        s2 = (h // 2) * W
        s3 = (h - h // 2) * W
        res = min(res, diff([s1, s2, s3]))

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

        s2 = (H // 2) * w
        s3 = (H - H // 2) * w
        res = min(res, diff([s1, s2, s3]))
        
        s2 = H * (w // 2)
        s3 = H * (w - w // 2)
        res = min(res, diff([s1, s2, s3]))

    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    solve(H, W)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

result = H * W
S = [None] * 3

"""
+--------------+
| S0 | S1 | S2 |
+--------------+
"""
if W >= 3:
    S_min = H * (W // 3)
    S_max = H * ((W + 2) // 3)
    result = min(result, S_max - S_min)

"""
+----+
| S0 |
+----+
| S1 |
+----+
| S2 |
+----+
"""
if H >= 3:
    S_min = W * (H // 3)
    S_max = W * ((H + 2) // 3)
    result = min(result, S_max - S_min)

"""
+----+----+
| S0 |    |
+----+ S2 |
| S1 |    |
+----+----+
"""
for w in range(1, W):
    S[0] = w * (H // 2)
    S[1] = w * ((H + 1) // 2)
    S[2] = (W - w) * H
    result = min(result, max(S) - min(S))

"""
+----+----+
| S0 | S1 |
+----+----+
|   S 2   |
+---------+
"""
for h in range(1, H):
    S[0] = h * (W // 2)
    S[1] = h * ((W + 1) // 2)
    S[2] = (H - h) * W
    result = min(result, max(S) - min(S))

print(result)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if(h%3==0 or w%3==0):
    print(0)
    quit()
def main(h,w):
    a=h
    for i in range(1,h//2+1):
        l=[i*w,(h-i)*(w//2),(h-i)*(w-w//2)]
        a=min(max(l)-min(l),a)
    return a
print(min(main(h,w),main(w,h)))

Submission status: Accepted

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

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

a = []
a.append([H//3*W, (H-H//3)*(W//2), (H-H//3)*(W//2+W%2)])
a.append([(H//3 + 1)*W, (H-H//3-1)*(W//2), (H-H//3-1)*(W//2+W%2)])
t = W
W = H
H = t
a.append([H//3*W, (H-H//3)*(W//2), (H-H//3)*(W//2+W%2)])
a.append([(H//3 + 1)*W, (H-H//3-1)*(W//2), (H-H//3-1)*(W//2+W%2)])

ans = min(W, H)
for i in range(len(a)):
    if  not 0 in a[i]:
        ans = min(ans, max(a[i]) - min(a[i]))


print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

from itertools import accumulate

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def yoko(h, w):
    return 0 if h%3 == 0 else w

def tate(h, w):
    return 0 if w%3 == 0 else h

def tee1(h, w):
    h1 = h//3
    w1 = w//2

    top = h1 * w
    lef = (h-h1)*w1
    rig = (h-h1)*(w-w1)

    return max(abs(top-lef), abs(top-rig), abs(lef-rig))

def tee2(h, w):
    h1 = h // 3 + 1
    w1 = w // 2

    top = h1 * w
    lef = (h - h1) * w1
    rig = (h - h1) * (w - w1)

    return max(abs(top - lef), abs(top - rig), abs(lef - rig))

def to1(h, w):
    w1 = w//3
    h1 = h//2

    lef = w1*h
    top = (w-w1)*h1
    bot = (w-w1)*(h-h1)

    return max(abs(lef-top), abs(lef-bot), abs(top-bot))


def to2(h, w):
    w1 = w // 3 + 1
    h1 = h // 2

    lef = w1 * h
    top = (w - w1) * h1
    bot = (w - w1) * (h - h1)

    return max(abs(lef - top), abs(lef - bot), abs(top - bot))


def judge(h, w):
    return min(yoko(h, w), tate(h, w), tee1(h, w), tee2(h, w), to1(h, w), to2(h, w))

h, w = li()

ans = judge(h, w)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=h*w
for i in range(1,h):
  a=i*w
  b=(h-i)*int(w/2)
  c=h*w-a-b
  if ans>(max(a,b,c)-min(a,b,c)):
    ans=max(a,b,c)-min(a,b,c)
for i in range(1,h):
  a=i*w
  b=w*int((h-i)/2)
  c=h*w-a-b
  if ans>(max(a,b,c)-min(a,b,c)):
    ans=max(a,b,c)-min(a,b,c)

for i in range(1,w):
  a=i*h
  b=(w-i)*int(h/2)
  c=h*w-a-b
  if ans>(max(a,b,c)-min(a,b,c)):
    ans=max(a,b,c)-min(a,b,c)
for i in range(1,w):
  a=i*h
  b=h*int((w-i)/2)
  c=h*w-a-b
  if ans>(max(a,b,c)-min(a,b,c)):
    ans=max(a,b,c)-min(a,b,c)
print(ans)

Submission status: Accepted

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

m = 100000000000000

if (H%3)==0:
  m = min(m,0)
else:
  m = min(m,W)
  
if (W%3)==0:
  m = min(m,0)
else:
  m = min(m,H)

 
R = 100
for dh in range(-R,R):
  for dw in range(-R,R):
    S1 = H*(W//3+dw)
    S2 = (H//2+dh)*(W-W//3-dw)
    S3 = (H-H//2-dh)*(W-W//3-dw)
    if ( (W//3+dw)<0 or (H//2+dh)<0 or (H//2-dh)<0 or (W-W//3-dw)<0 or (H-H//2-dh)<0 ):
      continue
    m = min(m,max([S1,S2,S3])-min([S1,S2,S3]))
 
for dh in range(-R,R):
  for dw in range(-R,R):
    S1 = W*(H//3+dw)
    S2 = (W//2+dh)*(H-H//3-dw)
    S3 = (W-W//2-dh)*(H-H//3-dw)
    if ( (H//3+dw)<0 or (W//2+dh)<0 or (W//2-dh)<0 or (H-H//3-dw)<0 or (W-W//2-dh)<0  ):
      continue
    m = min(m,max([S1,S2,S3])-min([S1,S2,S3]))

print ( m )

Submission status: Accepted

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

if H%3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = 10 ** 11
    for i in range(W):
        if i == 0:
            j = (H//3)
            k = (H-j)//2
            s1 = W * j
            s2 = W * k
            s3 = W * (H-j-k)
            M = max(s1,s2,s3) - min(s1,s2,s3)
            ans = min(ans,M)
            continue
        s1 = i * H
        j = H //2
        s2 = (W-i) * j
        s3 = (W-i) * (H-j)
        M = max(s1,s2,s3) - min(s1,s2,s3)
        ans = min(ans,M)
        
    tmp = W
    W = H
    H = tmp
    
    for i in range(W):
        if i == 0:
            j = (H//3)
            k = (H-j)//2
            s1 = W * j
            s2 = W * k
            s3 = W * (H-j-k)
            M = max(s1,s2,s3) - min(s1,s2,s3)
            ans = min(ans,M)
            continue
        s1 = i * H
        j = H //2
        s2 = (W-i) * j
        s3 = (W-i) * (H-j)
        M = max(s1,s2,s3) - min(s1,s2,s3)
        ans = min(ans,M)
        
    print(ans)

Submission status: Accepted

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

if (H * W) % 3 == 0:
    print(0)
else:
    ans = [0, 0, 0, 0]
    for i in range(2):
        H_left = H - (H // 3 + i)
        first = (H // 3 + i) * W
        if (H_left * W) % 2 == 0:
            second = third = H_left * W / 2
        else:
            second = (H_left * W) - (max(H_left, W) // 2) * min(H_left, W)
            third = (H_left * W) - second
        ans[i] = max(first, second, third) - min(first, second, third)
    for i in range(2):
        W_left = W - (W // 3 + i)
        first = (W // 3 + i) * H
        if (W_left * H) % 2 == 0:
            second = third = W_left * H / 2
        else:
            second = (W_left * H) - (max(W_left, H) // 2) * min(W_left, H)
            third = (W_left * H) - second
        ans[i+2] = max(first, second, third) - min(first, second, third)
    print(int(min(ans)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
def f(h,w):
    if h%3==0:
        return 0
    rt=h*w
    for i in range(1,h):
        rt=min(rt,max(i*w,(h-i)*(w//2),(h-i)*(w-(w//2))) - min(i*w,(h-i)*(w//2),(h-i)*(w-(w//2))))
        rt=min(rt,max(i*w,((h-i)//2)*w,(h-i-((h-i)//2))*w) - min(i*w,((h-i)//2)*w,(h-i-((h-i)//2))*w))
    return rt

print(min(f(h,w),f(w,h)))

Submission status: Accepted

Solution code:
from math import floor, ceil
from itertools import chain

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

# ある1ピースを i*W または j*W となるように切ったときのS_max - S_minをすべて求める
ans = min(
    max(a, b, c) - min(a, b, c)
    for a, b, c in chain(
        (
            (i * W, (H - i) * floor(W / 2), (H - i) * ceil(W / 2))
            for i in range(1, H)
        ),
        (
            (i * W, floor((H - i) / 2) * W, ceil((H - i) / 2) * W)
            for i in range(1, H)
        ),
        (
            (j * H, (W - j) * floor(H / 2), (W - j) * ceil(H / 2))
            for j in range(1, W)
        ),
        (
            (j * H, floor((W - j) / 2) * H, ceil((W - j) / 2) * H)
            for j in range(1, W)
        ),
    )
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

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

def solve(h,w):
    res = inf
    for i in range(1,h):
        a = i
        b = h-i
        c = w//2
        d = -(-w//2)
        s1 = [a*w,b*c,b*d]
        d1 = max(s1) - min(s1)
        c = b//2
        d = -(-b//2)
        s2 = [a*w,c*w,d*w]
        d2 = max(s2) - min(s2)
        d = min(d1,d2)
        res = min(res,d)
    return res

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

Submission status: Accepted

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


for i in range(2):
    if i == 0:
        ver, hori = H, W
    else:
        ver, hori = W, H
    for ha in range(1, ver):
        sa = ha * hori
        h = ver - ha
        
        # Case1 横二本の区切り線
        if h % 2 == 0:
            hb, hc = h // 2, h // 2
        else:
            hb, hc = h // 2, h // 2 + 1
        sb1, sc1 = hb * hori, hc * hori
        diff1 = max(sa, sb1, sc1) - min(sa, sb1, sc1)
        
        # Case2 横一本、縦一本区切り線
        if hori % 2 == 0:
            wb, wc = hori // 2, hori // 2
        else:
            wb, wc = hori // 2, hori // 2 + 1
        sb2, sc2 = h * wb, h * wc
        diff2 = max(sa, sb2, sc2) - min(sa, sb2, sc2)
        
        tmp_min =  min(diff1, diff2)
        ans = min(ans, tmp_min)


print(ans)

Submission status: Accepted

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


for ha in range(1, H):
    sa = ha * W
    h = H - ha
    
    # Case1 横日本の区切り線
    if h % 2 == 0:
        hb, hc = h // 2, h // 2
    else:
        hb, hc = h // 2, h // 2 + 1
    sb1, sc1 = hb * W, hc * W
    diff1 = max(sa, sb1, sc1) - min(sa, sb1, sc1)
    
    # Case2 横一本、縦一本区切り線
    if W % 2 == 0:
        wb, wc = W // 2, W // 2
    else:
        wb, wc = W // 2, W // 2 + 1
    sb2, sc2 = h * wb, h * wc
    diff2 = max(sa, sb2, sc2) - min(sa, sb2, sc2)
    
    tmp_min =  min(diff1, diff2)
    ans = min(ans, tmp_min)

# 縦横入れ替え
for ha in range(1, W):
    sa = ha * H
    h = W - ha
    
    # Case1 横日本の区切り線
    if h % 2 == 0:
        hb, hc = h // 2, h // 2
    else:
        hb, hc = h // 2, h // 2 + 1
    sb1, sc1 = hb * H, hc * H
    diff1 = max(sa, sb1, sc1) - min(sa, sb1, sc1)
    
    # Case2 横一本、縦一本区切り線
    if H % 2 == 0:
        wb, wc = H // 2, H // 2
    else:
        wb, wc = H // 2, H // 2 + 1
    sb2, sc2 = h * wb, h * wc
    diff2 = max(sa, sb2, sc2) - min(sa, sb2, sc2)
    
    tmp_min =  min(diff1, diff2)
    ans = min(ans, tmp_min)


print(ans)

Submission status: Accepted

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

S = H * W
diff = 10 ** 12
for i in range(1, H-1):
    S_up = i * W
    S_under = W * ((H - i) // 2)
    S_middle = S - S_up - S_under
    S_max = max(S_up, S_under, S_middle)
    S_min = min(S_up, S_under, S_middle)
    diff = min(diff, abs(S_max - S_min))

for i in range(1, W-1):
    S_up = i * H
    S_under = H * ((W - i) // 2)
    S_middle = S - S_up - S_under
    S_max = max(S_up, S_under, S_middle)
    S_min = min(S_up, S_under, S_middle)
    diff = min(diff, abs(S_max - S_min))

for i in range(1, H):
    S_up = i * W
    S_under = (W // 2) * (H - i)
    S_middle = S - S_up - S_under
    S_max = max(S_up, S_under, S_middle)
    S_min = min(S_up, S_under, S_middle)
    diff = min(diff, abs(S_max - S_min))

for i in range(1, W):
    S_up = i * H
    S_under = (H // 2) * (W - i)
    S_middle = S - S_up - S_under
    S_max = max(S_up, S_under, S_middle)
    S_min = min(S_up, S_under, S_middle)
    diff = min(diff, abs(S_max - S_min))

print(diff)

Submission status: Accepted

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

if (H * W) % 3 == 0:
    # 縦または横が3の倍数
    print(0)
elif H == 1 or W == 1:
    # 縦または横が1
    print(1)
else:
    ans = 9999999999
    # pattern1
    for i in range(1, H):
        l = [W * (H - i), i * (int(W / 2)), i * (W - int(W / 2))]
        l.sort()
        ans = min(ans, l[-1] - l[0])

    # pattern2
    for i in range(1, W):
        l = [H * (W - i), i * (int(H / 2)), i * (H - int(H / 2))]
        l.sort()
        ans = min(ans, l[-1] - l[0])

    # pattern3
    ans = min(ans, H)

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

c = min(max(abs(w//3*h - (h+1)//2*(w-w//3)), abs(w//3*h - h//2*(w-w//3))), max(abs((w//3+1)*h - (h+1)//2*(w-w//3-1)), abs((w//3+1)*h - h//2*(w-w//3-1))))
d = min(max(abs(h//3*w - (w+1)//2*(h-h//3)), abs(h//3*w - w//2*(h-h//3))), max(abs((h//3+1)*w - (w+1)//2*(h-h//3-1)), abs((h//3+1)*w - w//2*(h-h//3-1))))

print(min(w,h,c,d))

Submission status: Accepted

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

Submission status: Accepted

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

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


def c(H, W):
    r = 1000000000000000000000000000000
    for y in range(1, H):
        l = [W * y, (W // 2) * (H - y), (W - W // 2) * (H - y)]
        r = min(r, max(l) - min(l))
    return r

ans=min(c(h, w), c(w, h))
if h > 3:
    ans = min(ans, w)
if w > 3:
    ans=min(ans,h)
print(ans)

Submission status: Accepted

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

def solve(h,w):
    ans = min(h,w)
    for i in range(1,h):
        p1 = w*i
        p2 = (h-i)*(w//2)
        p3 = h*w-p1-p2
        ans = min(ans, max(p1,p2,p3)-min(p1,p2,p3))
    return ans 

ans = min(solve(h,w), solve(w,h))
if h*w % 3 == 0:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


H, W = MI()
mini_a = INF
mini_b = INF
mini1 = INF
mini2 = INF
mini3 = INF
mini4 = INF
for h in range(1,H):
    sa = h * W
    sb = (H-h) * math.floor(W/2)
    sc = (H-h) * (W - math.floor(W/2))
    sd = (math.floor((H-h)/2)) * W
    se = (H-h-math.floor((H-h)/2)) * W
    mini1 = min(mini1, max(sa,max(sb,sc)) - min(sa,min(sb,sc)))
    mini2 = min(mini2, max(sa,max(sd,se)) - min(sa,min(sd,se)))
    mini_a = min(mini1,mini2)
for w in range(1,W):
    sa = H * w
    sb = (W-w) * math.floor(H/2)
    sc = (W-w) * (H - math.floor(H/2))
    sd = (math.floor((W-w)/2)) * H
    se = (W-w-math.floor((W-w)/2)) * H
    mini3 = min(mini3, max(sa,max(sb,sc)) - min(sa,min(sb,sc)))
    mini4 = min(mini4, max(sa,max(sd,se)) - min(sa,min(sd,se)))
    mini_b = min(mini3,mini4)
print(min(mini_a,mini_b))

Submission status: Accepted

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

def solve2(h, w):
  l = h // 2
  s1 = l * w
  s2 = (h - l) * w
  return s1, s2

def solve(h, w):
  mn = 1e10
  for i in range(1, h):
    s1 = i * w
    s2, s3 = solve2(h - i, w)
    dif1 = (max(s1, s2, s3) - min(s1, s2, s3))
    s4, s5 = solve2(w, h - i)
    dif2 = (max(s1, s4, s5) - min(s1, s4, s5))
    mn = min(mn, dif1, dif2)
  return mn

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = h * w
if s % 3 == 0:
    ans = 0
else:
    c = []
    for i in range(1, h):
        sa = i * w
        sb = (h - i) * (w // 2)
        sc = (h - i) * (w - (w // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
        sb = ((h - i) // 2) * w
        sc = s - sa - sb
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    for i in range(1, w):
        sa = i * h
        sb = (w - i) * (h // 2)
        sc = (w - i) * (h - (h // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
        sb = ((w - i) // 2) * h
        sc = s - sa - sb
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    ans = min(c)
print(ans)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')


def maxdiff(s1, s2, s3):
    return max(abs(s1-s2), abs(s2-s3), abs(s3-s1))

def solve():
    h,w = f()
    ans = int(1e10)

    for hc in range(h):
        s1 = hc * w

        h2 = (h-hc)//2
        h3 = h - hc -h2
        s2 = h2 * w
        s3 = h3 * w

        ans = min(ans, maxdiff(s1, s2, s3))

        w1 = w//2
        w2 = w - w1
        s2 = w1 * (h-hc)
        s3 = w2 * (h-hc)
        ans = min(ans, maxdiff(s1, s2, s3))


    for wc in range(w):
        s1 = wc * h

        w2 = (w-wc)//2
        w3 = w - wc -w2
        s2 = w2 * h
        s3 = w3 * h

        ans = min(ans, maxdiff(s1, s2, s3))

        h1 = h//2
        h2 = h - h1
        s2 = h1 * (w-wc)
        s3 = h2 * (w-wc)
        ans = min(ans, maxdiff(s1, s2, s3))



    print(ans)



solve()

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
if a%3==0 or b%3==0:
  print(0)
elif a==2 and b==2:
  print(1)
else:
  c=a//3+((a/3-a//3)>.5)
  d=a-c
  e=b//3+((b/3-b//3)>.5)
  f=b-e
  g=a//2
  h=a-g
  i=b//2
  j=b-i
  m=[b*c,d*i,d*j]
  n=[a*e,f*g,f*h]
  print(min(max(m)-min(m),max(n)-min(n),a,b))

Submission status: Accepted

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

res = 10**18

if(h%3)==0:
    res = min(res,0)
else:
    res = min(res,w)
if(w%3)==0:
    res = min(res,0)
else:
    res = min(res,h)

#-------
#   |
for i in range(1,min(h//2+2,h)):
    row = i*w
    left =(h-i)* ((w//2)+(w%2))
    right = (h-i)*(w//2)
    res = min(res,max(left,row)-min(row,right)) 
#|
#|
#|-----------
#|
#|
for i in range(1,min(w//2+2,w)):
    col = h * i
    up = (w-i) * ((h//2)+(h%2))
    down = (w-i) *(h//2)
    res = min(res, max(up,col)-min(down,col))

print(res)