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:
a, b = map(int, input().split())
ans = int(1e18)

def check(l):
    return max(l) - min(l)

if a % 3 == 0 or b % 3 == 0:
    ans = 0
else:
    x = a // 3
    y = a - x
    box = [x*b, b*(y//2), b*(y//2 + y%2)]
    ans = min(ans, check(box))
    box = [x*b, y*(b//2), y*(b//2 + b%2)]
    ans = min(ans, check(box))
    
    x = a // 3 + 1
    y = a - x
    box = [x*b, b*(y//2), b*(y//2 + y%2)]
    ans = min(ans, check(box))
    box = [x*b, y*(b//2), y*(b//2 + b%2)]
    ans = min(ans, check(box))

    (a, b) = (b, a)
    x = a // 3
    y = a - x
    box = [x*b, b*(y//2), b*(y//2 + y%2)]
    ans = min(ans, check(box))
    box = [x*b, y*(b//2), y*(b//2 + b%2)]
    ans = min(ans, check(box))
    
    x = a // 3 + 1
    y = a - x
    box = [x*b, b*(y//2), b*(y//2 + y%2)]
    ans = min(ans, check(box))
    box = [x*b, y*(b//2), y*(b//2 + b%2)]
    ans = min(ans, check(box))


print(ans)

Submission status: Accepted

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

def get_ans(A, B):
    ans = A * B
    for A1 in range(1, A):
        A2 = (A - A1) // 2
        A3 = A - A1 - A2
        S = [A1 * B, A2 * B, A3 * B]
        ans = min(ans, max(S) - min(S))

    for A1 in range(1, A):
        B2 = B // 2
        B3 = B - B2
        S = [A1 * B, (A - A1) * B2, (A - A1) * B3]
        ans = min(ans, max(S) - min(S))

    return ans

print(min(get_ans(H, W), get_ans(W, H)))

Submission status: Accepted

Solution code:
def solve(H, W):
    s = [0]*3
    ans = H*W
    for h in range(H):
        s[0] = W * h
        s[1] = (H - h) * (W // 2)
        s[2] = H * W - s[0] - s[1]
        if max(s) - min(s) < ans:
            ans = max(s) - min(s)
        if ans == 0:
            print(ans)
            exit()
    for h in range(H):
        s[0] = h * W
        s[1] = (H - h) // 2 * W
        s[2] = H * W - s[0] - s[1]
        if max(s) - min(s) < ans:
            ans = max(s) - min(s)
        if ans == 0:
            print(ans)
            exit()
    return ans

H, W = [int(i) for i in input().split()]
ans = solve(H,W)
ans2 = solve(W,H)

print(min(ans,ans2))

Submission status: Accepted

Solution code:
from collections import defaultdict
 
 
def calc(H, W):
    if H % 3 == 0 or W % 3 == 0:
        return 0
    ans = min(H, W)
    h1 = H // 2
    h2 = H - h1
    for w in range(W + 1):
        a = H * w
        b = (W - w) * h1
        c = (W - w) * h2
        ans = min(ans, max(abs(a - b), abs(a - c)))
    return ans
 
 
def solve(H, W):
    return min(calc(H, W), calc(W, H))
 
 
def main():
    H, W = map(int, input().split())
    print(solve(H, W))
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=[int(x) for x in input().split()]
if h%3==0 or w%3==0:
    s=0
elif h==1 or w==1:
    s=1
else:
    s=float("inf")
    def diff(a,b):
        shen=b//2
        tmpS=float("inf")
        for i in range(1,a):
            p1=i*b
            hen=(a-i)//2
            p2=hen*b
            p3=(a-hen-i)*b
            q2=(a-i)*shen
            q3=(a-i)*(b-shen)
            tmpS=min(tmpS,max(p1,p2,p3)-min(p1,p2,p3),max(p1,q2,q3)-min(p1,q2,q3))
        return tmpS
    s=min(diff(h,w),diff(w,h))
print(s)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
res = min(H,W)
hr,vr = H%3*W,W%3*H
def min_s_diff(x, y):
    if x % 3 == 0:
        return 0
    if x % 3 == 1:
        a = x // 3
        b = y // 2
        s1 = a * y
        s2 = (x - a) * b
        s3 = x * y - s1 - s2
        return max(s1, s2, s3) - min(s1, s2, s3)
    if x % 3 == 2:
        a = x // 3 + 1
        b = y // 2
        s1 = a * y
        s2 = (x - a) * b
        s3 = x * y - s1 -s2
        return max(s1, s2, s3) - min(s1, s2, s3)

print(min(min_s_diff(H, W), min_s_diff(W, H), res, hr, vr))

Submission status: Accepted

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

    minv = 100000000000
    for i in range(1, h):
        s = []
        s.append(i*w)
        j = w//2
        s.append((h-i)*j)
        s.append((h-i)*(w-j))
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)

        s = []
        s.append(i*w)
        j = (h-i)//2
        s.append(j*w)
        s.append((h-i-j)*w)
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)

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

        s = []
        s.append(i*w)
        j = (h-i)//2
        s.append(j*w)
        s.append((h-i-j)*w)
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)
    print(minv)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def div(h, w):
    S1, S2, S3 = 0, 0, 0
    mw = w // 2
    ans = 10 ** 10
    for i in range(1, h):
        mh = (h-i) // 2
        S1 = i * w
        for j in range(2):
            if j == 0:
                S2 = (h-i) * mw
                S3 =  (h-i) * (w-mw)
            else:
                S2 = mh * w
                S3 = (h-i-mh) * w

            maxS = max(S1, S2, S3)
            minS = min(S1, S2, S3)
            diff = maxS-minS
            ans = min(ans, diff)
    return ans

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

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    hold = 0
else:
    for h in range(H):
        if W % 2 == 0:
            Sa = h * W
            Sb = (H - h) * (W / 2)
            Sc = (H - h) * (W / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)
        else:
            Sa = h * W
            Sb = (H - h) * (( (W + 1) / 2) )
            Sc = (H - h) * (( (W - 1) / 2) )
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)

    for w in range(W):
        if H % 2 == 0:
            Sa = H * w
            Sb = (W - w) * (H / 2)
            Sc = (W - w) * (H / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)
        else:
            Sa = H * w
            Sb = (W - w) * ((H + 1) / 2)
            Sc = (W - w) * ((H - 1) / 2)
            diff = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            hold = min(hold, diff)

hold = min(hold, H, W)

print(int(hold))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
res = min(H,W)
hr,ht,vr,vt = 0,0,0,0
hr,vr = H%3*W,W%3*H
def t(x,y):
    if x%3==0:
        return 0
    elif x%3==1:
        a = ((x//3)*2+1)*(y//2)
        b = x//3*y
        c = x*y-a-b
        return max(a,b,c)-min(a,b,c)
    else:
        a = ((x//3)*2+1)*(y//2)
        b = (x//3+1)*y
        c = x*y-a-b
        return max(a,b,c)-min(a,b,c)
ht = t(H,W)
vt = t(W,H)
print(min(res,hr,ht,vr,vt))

Submission status: Accepted

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

minv = 99999999

for i in range(1, h):
    s1 = i*w
    
    if (h-i)*w % 2 == 0:
        s2 = (h-i)* w / 2
        s3 = (h-i)* w / 2
    else:
        s2 = min((h-i), w) * (max((h-i), w)//2)
        s3 = min((h-i), w) * (1+max((h-i), w)//2)
        
    if max(s1, s2, s3) - min(s1, s2, s3) < minv:
        minv = max(s1, s2, s3) - min(s1, s2, s3)
        

for i in range(1, w):
    s1 = i*h
    
    if h*(w-i) % 2 == 0:
        s2 = h*(w-i) / 2
        s3 = h*(w-i) / 2
    else:
        s2 = min(h, (w-i)) * (max(h, (w-i))//2)
        s3 = min(h, (w-i)) * (1+max(h, (w-i))//2)
        
    if max(s1, s2, s3) - min(s1, s2, s3) < minv:
        minv = max(s1, s2, s3) - min(s1, s2, s3)
        
print(int(minv))

Submission status: Accepted

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

for h in range(1,H):
    Sa = h * W
    Sb = (H - h) * (W // 2)
    Sc = (H - h) * (W - ( W //2 ))
    if max(Sa,Sb,Sc) - min(Sa,Sb,Sc) < h_ans:
        h_ans = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
        
for h in range(1,H):
    Sa = h * W
    Sb = ((H - h)//2) * W
    Sc = (H - (h + (H-h)//2)) * W
    if max(Sa,Sb,Sc) - min(Sa,Sb,Sc) < h_ans:
        h_ans = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
    
for w in range(1,W):
    Sa = H * w
    Sb = (H // 2) * (W - w)
    Sc = (H - (H //2)) * (W - w)
    if max(Sa,Sb,Sc) - min(Sa,Sb,Sc) < w_ans:
        w_ans = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
    
for w in range(1,W):
    Sa = H * w
    Sb = H * ((W -w)//2)
    Sc = H * (W - (w + (W -w)//2) ) 
    if max(Sa,Sb,Sc) - min(Sa,Sb,Sc) < w_ans:
        w_ans = max(Sa,Sb,Sc) - min(Sa,Sb,Sc)
    
        
print((min(h_ans,w_ans)))

Submission status: Accepted

Solution code:
#ABC062C

h,w=map(int,raw_input().split())
res=[]
#case1
s1=(h/3)*w
s2=(h-h/3)*(w/2)
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case2
s1=((h/3)+1)*w
s2=(h-h/3-1)*(w/2)
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case3
s1=s2=(h/3)*w
s3=h*w-2*s1
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case4
s1=(h/3)*w
s2=(h/3+1)*w
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))

w,h=h,w
#case5
s1=(h/3)*w
s2=(h-h/3)*(w/2)
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case5
s1=((h/3)+1)*w
s2=(h-h/3-1)*(w/2)
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case7
s1=s2=(h/3)*w
s3=h*w-2*s1
s=[s1,s2,s3]
res.append(max(s)-min(s))
#case8
s1=(h/3)*w
s2=(h/3+1)*w
s3=h*w-s1-s2
s=[s1,s2,s3]
res.append(max(s)-min(s))
print min(res)

Submission status: Accepted

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

ans=[]
### case1  000
ans.append(0 if h%3==0 else w)
###case 2 tate 000
ans.append(0 if w%3==0 else h)

def getmin(h, w):
    area=9999999999999
    for i in range(h//3-3, h//3+2):
        for j in range(w//2 -3, w//2 +3):
            areas=[ i * w, j * (h-i), (w-j)*(h-i)]
            area = max(areas)-min(areas) if area > max(areas)-min(areas) else area
    return area

ans.append(getmin(h, w))
ans.append(getmin(w, h))

print(min(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict


def calc(H, W):
    if H % 3 == 0 or W % 3 == 0:
        return 0
    ans = min(H, W)
    h1 = H // 2
    h2 = H - h1
    for w in range(W + 1):
        a = H * w
        b = (W - w) * h1
        c = (W - w) * h2
        ans = min(ans, max(abs(a - b), abs(a - c)))
    return ans


def solve(H, W):
    return min(calc(H, W), calc(W, H))


def main():
    H, W = map(int, input().split())
    print(solve(H, W))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
H, W = map(int, input().split())
factors = []
for h1 in range(1,H):
    subHeight = H-h1
    h2 = subHeight//2
    h3 = subHeight-h2
    w2 = W//2
    w3 = W-w2
    s1 = [ h1*W, h2*W, h3*W ]
    s2 = [ h1*W, subHeight*w2, subHeight*w3 ]
    factors.append(max(s1)-min(s1))
    factors.append(max(s2)-min(s2))

for w1 in range(1,W):
    subWidth = W-w1
    w2 = subWidth//2
    w3 = subWidth-w2
    h2 = H//2
    h3 = H-h2
    s1 = [ H*w1, H*w2, H*w3 ]
    s2 = [ H*w1, h2*subWidth, h3*subWidth ]
    factors.append(max(s1)-min(s1))
    factors.append(max(s2)-min(s2))

print(min(factors))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np

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

m = 10000000000000000000000000
m = min(m, (1 if h % 3 else 0) * w)
m = min(m, (1 if w % 3 else 0) * h)
for _ in range(2):
    for i in range(1, h+1):
        v = np.array([i*w, w//2*(h-i), (w-w//2)*(h-i)])
        m = min(m, max(v) - min(v))
    h, w = w, h

print(m)

Submission status: Accepted

Solution code:
import math


def main():
    """
    H * W 板チョコ3分割
    面積：A B C
    minimize(max(A B C) - min(A B C))

    縦or横がMAX、片方が途中まで
    上記1つと、残りを半分
    残り：面積２以上
    """
    H, W = list(map(int, input().strip().split()))
    # 縦MAX, H>=2より、W-1まで確認
    # 横MAX, H>=2より、W=1のとき３分割できないので、W>=2
    answer = calc_answer(H, W)
    answer = calc_answer(W, H, answer=answer)
    print(answer)


def calc_answer(H, W, answer=None):
    if answer is None:
        answer = float("inf")

    for _w in range(1, math.ceil(W / 2) + 1):
        # 縦MAXで試す
        S = [
            H * _w,
            H * math.ceil((W - _w) / 2),
            H * int((W - _w) // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(H, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

        # 横MAXで縦分割
        S = [
            H * _w,
            (W - _w) * math.ceil(H / 2),
            (W - _w) * int(H // 2),
        ]
        if not 0 in S:
            S_diff = max(S) - min(S)
            #print(_h, _w, S, S_diff, answer, sep="\t")
            answer = min(answer, S_diff)

    return answer

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def Choco(H,W,ans):
    if H%3==0 or W%3==0:
        print("0")
        exit()
    else:
        for i in range(H):
            if i==0:
                pass
            else:
                a=W*i
                if (H-i)%2==0:
                    b=(H-i)*W//2
                    dif=abs(a-b)
                else:
                    w1=W//2
                    b=(H-i)*w1
                    c=(H-i)*(W-w1)
                    M=max(a,b,c)
                    m=min(a,b,c)
                    dif=M-m
                ans=min(dif,ans)
    return ans

ans=float("inf")
ans=Choco(H,W,ans)
ans=Choco(W,H,ans)

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
def calc(h, w):
    best = h*w
    for h1 in range(1, h):
        s1 = h1 * w
        s2 = (h - h1) * (w/2)
        s3 = h * w - s1 - s2
        best = min(best, max([s1, s2, s3]) - min([s1, s2, s3]))
        s2 = ((h - h1)/2) * w
        s3 = h * w - s1 - s2
        best = min(best, max([s1, s2, s3]) - min([s1, s2, s3]))
    return best
print min(calc(H, W), calc(W, H))

Submission status: Accepted

Solution code:
import math

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

def func(h,w,ans):
    for i in range(1,h+1):

        if((h-i) % 2 == 0): 
            a = i*w
            b = ( (h-i)//2 )*w
            s = abs(a-b)
            ans = min(s,ans)
    
        else:
            a = i * w 
            w1 = w//2 
            b = (h-i)*w1
            c = (h-i)*(w-w1)
            M = max(a,b,c)
            m = min(a,b,c)
            s = M-m
            ans = min(s,ans)
    return ans

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

ans = float('inf')

ans = func(H,W,ans)
ans = func(W,H,ans)

print(ans)

Submission status: Accepted

Solution code:
import math

def ty(h,w):
    lenh=h/2
    if h%2==0:
        #tateb
        tatew = math.ceil(w/3)
        maxb = max(h*tatew, (w-tatew)*lenh)
        minb = min(h*tatew, (w-tatew)*lenh)
        res0 = maxb-minb
        #tates
        if w>3:
            tatew = math.floor(w/3)
            maxb = max(h*tatew, (w-tatew)*lenh)
            minb = min(h*tatew, (w-tatew)*lenh)
        res1 = maxb-minb
    else:
        #tateb
        tatew = math.ceil(w/3)
        maxb = max(h*tatew, (w-tatew)*math.ceil(lenh))
        minb = min(h*tatew, (w-tatew)*math.floor(lenh))
        res0 = maxb-minb
        #tates
        if h>3:
            tatew = math.floor(w/3)
            maxb = max(h*tatew, (w-tatew)*math.ceil(lenh))
            minb = min(h*tatew, (w-tatew)*math.floor(lenh))
        res1 = maxb-minb
    return math.floor(min(res0,res1))

h,w = map(int, input().split())
result = [100000,100000,100000, 100000]

#tate3
if h%3==0:
    result[0] = 0
elif h>3:
    result[0] = w
#yoko3
if w%3==0:
    result[1] = 0
elif w>3:
    result[1] = h

#ト
if w%3==0:
    if h%2==0:
        result[2] = 0
    elif h>2:
        result[2] = math.floor(2*w/3)
else:
    result[2] = ty(h,w)
#T
if h%3==0:
    if w%2==0:
        result[3] = 0
    elif w>2:
        result[3] = math.floor(2*h/3)
else:
    result[3] = ty(w,h)
print(min(result))

Submission status: Accepted

Solution code:
import os
import sys
import math

def func(h, w, ans):
    for i in range(1, w + 1):
        first = h * i

        if (w - i) % 2 == 0:
            second = h * ((w - i) // 2)
            s = abs(first - second)
            ans = min(s, ans)
        else:
            second = h * ((w - i) // 2)
            third = h * (w - i - (w - i) // 2)
            s = max(abs(first - second), abs(second - third), abs(third - first))
            ans = min(s, ans)

        if h % 2 == 0:
            second = (h // 2) * (w - i)
            s = abs(first - second)
            ans = min(s, ans)
        else:
            second = (h // 2) * (w - i)
            third = (h - (h // 2)) * (w - i)
            s = max(abs(first - second), abs(second - third), abs(third - first))
            ans = min(s, ans)
    return ans

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

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

ans = float('inf')

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

Submission status: Accepted

Solution code:
import math
import sys
 
T = list(map(int, input().split()))
S = T[0] * T[1]
 
if ((T[0] % 3 == 0) or (T[1] % 3 == 0)):
    print(0)
    sys.exit()
 
minS = 1000000000000
for i in range(1, math.ceil(T[0]/2)+1):
    A = i * T[1]
    F = math.floor(T[1] / 2) * (T[0] - i)
    C = S - (A + F)
    if (F == C):
        minS = min(minS, abs(A - F))
    else:
        if (A > C):
            minS = min(minS, abs(A - F))
        elif(C >= A and A >= F):
            minS = min(minS, abs(C - F))
        else:
            minS = min(minS, abs(C - A))
    A = i * T[1]
    F = math.floor((T[0] - i) / 2) * T[1]
    C = S - (A + F)
    if (F == C):
        minS = min(minS, abs(A - F))
    else:
        if (A > C):
            minS = min(minS, abs(A - F))
        elif(C >= A and A >= F):
            minS = min(minS, abs(C - F))
        else:
            minS = min(minS, abs(C - A))
 
for i in range(1, math.ceil(T[1]/2) + 1):
    A = i * T[0]
    F = math.floor(T[0] / 2) * (T[1] - i)
    C = S - (A + F)
    if (F == C):
        minS = min(minS, abs(A - F))
    else:
        if (A > C):
            minS = min(minS, abs(A - F))
        elif(C >= A and A >= F):
            minS = min(minS, abs(C - F))
        else:
            minS = min(minS, abs(C - A))
    A = i * T[0]
    F = math.floor((T[1] - i) / 2) * T[0]
    C = S - (A + F)
    if (F == C):
        minS = min(minS, abs(A - F))
    else:
        if (A > C):
            minS = min(minS, abs(A - F))
        elif(C >= A and A >= F):
            minS = min(minS, abs(C - F))
        else:
            minS = min(minS, abs(C - A))
 
print(minS)

Submission status: Accepted

Solution code:
def check_s(tmp1, tmp2, tmp3):
    S_min = 2 ** 50
    S_max = 0
    S_min = min(S_min, tmp1, tmp2, tmp3)
    S_max = max(S_max, tmp1, tmp2, tmp3)
    return S_max - S_min

if __name__ == "__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()

    result = 2 ** 50
    for x in range(1, W + 1):
        H1 = H // 2
        H2 = H - H1

        W1 = x
        W2 = W - W1

        W3 = W2 // 2
        W4 = W2 - W3

        tmp1 = W1 * H
        tmp2 = W3 * H
        tmp3 = W4 * H

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = W1 * H
        tmp2 = W2 * H1
        tmp3 = W2 * H2
        result = min(result, check_s(tmp1, tmp2, tmp3))

    for y in range(1,  H+ 1):
        H1 = y
        H2 = H - H1

        H3 = H2 // 2
        H4 = H3 - H2

        W1 = W // 2
        W2 = W - W1


        tmp1 = H1 * W
        tmp2 = H3 * W
        tmp3 = H4 * W

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = H1 * W
        tmp2 = H2 * W1
        tmp3 = H2 * W2
        result = min(result, check_s(tmp1, tmp2, tmp3))


    print (result)

Submission status: Accepted

Solution code:
def check1(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = H1 * W1
    res2 = H1 * W2
    res3 = H2 * (W1 + W2)
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check2(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = H1 * (W1 + W2)
    res2 = H2 * (W1)
    res3 = H2 * W2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check3(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = W1 * (H1 + H2)
    res2 = W2 * H1
    res3 = W2 * H2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check4(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = W2 * (H1 + H2)
    res2 = W1 * H1
    res3 = W1 * H2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check_s(tmp1, tmp2, tmp3):
    S_min = 2 ** 50
    S_max = 0
    S_min = min(S_min, tmp1, tmp2, tmp3)
    S_max = max(S_max, tmp1, tmp2, tmp3)
    return S_max - S_min

if __name__ == "__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()
    if (H == 2 and W == 2):
        print (1)
        exit()
    H1 = H // 2
    H2 = H - H1
    W1 = W // 2
    W2 = W - W1
    result = 2 ** 50
    result = min(result, check1(H1, H2, W1, W2))
    result = min(result, check2(H1, H2, W1, W2))
    result = min(result, check3(H1, H2, W1, W2))
    result = min(result, check4(H1, H2, W1, W2))

    for x in range(1, W + 1):
        H1 = H // 2
        H2 = H - H1

        W1 = x
        W2 = W - W1

        W3 = W2 // 2
        W4 = W2 - W3

        tmp1 = W1 * H
        tmp2 = W3 * H
        tmp3 = W4 * H

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = W1 * H
        tmp2 = W2 * H1
        tmp3 = W2 * H2
        result = min(result, check_s(tmp1, tmp2, tmp3))

    for y in range(1,  H+ 1):
        H1 = y
        H2 = H - H1

        H3 = H2 // 2
        H4 = H3 - H2

        W1 = W // 2
        W2 = W - W1


        tmp1 = H1 * W
        tmp2 = H3 * W
        tmp3 = H4 * W

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = H1 * W
        tmp2 = H2 * W1
        tmp3 = H2 * W2
        result = min(result, check_s(tmp1, tmp2, tmp3))


    print (result)

Submission status: Accepted

Solution code:
def check1(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = H1 * W1
    res2 = H1 * W2
    res3 = H2 * (W1 + W2)
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check2(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = H1 * (W1 + W2)
    res2 = H2 * (W1)
    res3 = H2 * W2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check3(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = W1 * (H1 + H2)
    res2 = W2 * H1
    res3 = W2 * H2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check4(H1, H2, W1, W2):
    S_min = 2 ** 50
    S_max = 0
    res1 = W2 * (H1 + H2)
    res2 = W1 * H1
    res3 = W1 * H2
    S_min = min(S_min, res1)
    S_min = min(S_min, res2)
    S_min = min(S_min, res3)
    S_max = max(S_max, res1)
    S_max = max(S_max, res2)
    S_max = max(S_max, res3)
    return S_max - S_min

def check_s(tmp1, tmp2, tmp3):
    S_min = 2 ** 50
    S_max = 0
    S_min = min(S_min, tmp1, tmp2, tmp3)
    S_max = max(S_max, tmp1, tmp2, tmp3)
    return S_max - S_min

if __name__ == "__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()

    H1 = H // 2
    H2 = H - H1
    W1 = W // 2
    W2 = W - W1
    result = 2 ** 50
    result = min(result, check1(H1, H2, W1, W2))
    result = min(result, check2(H1, H2, W1, W2))
    result = min(result, check3(H1, H2, W1, W2))
    result = min(result, check4(H1, H2, W1, W2))

    for x in range(1, W + 1):
        H1 = H // 2
        H2 = H - H1

        W1 = x
        W2 = W - W1

        W3 = W2 // 2
        W4 = W2 - W3

        tmp1 = W1 * H
        tmp2 = W3 * H
        tmp3 = W4 * H

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = W1 * H
        tmp2 = W2 * H1
        tmp3 = W2 * H2
        result = min(result, check_s(tmp1, tmp2, tmp3))

    for y in range(1,  H+ 1):
        H1 = y
        H2 = H - H1

        H3 = H2 // 2
        H4 = H3 - H2

        W1 = W // 2
        W2 = W - W1


        tmp1 = H1 * W
        tmp2 = H3 * W
        tmp3 = H4 * W

        result = min(result, check_s(tmp1, tmp2, tmp3))
        tmp1 = H1 * W
        tmp2 = H2 * W1
        tmp3 = H2 * W2
        result = min(result, check_s(tmp1, tmp2, tmp3))


    print (result)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
#横長パターンと縦長パターンのみ
ans=H*W
if H%3==0 or W%3==0:
  ans=0

#横長パターン
for h in range(H):
  A=h*W
  if W%2==0:
    B=(H-h)*(W/2)
    C=(H-h)*(W/2)
  else:
    B=(H-h)*(W+1)/2
    C=(H-h)*(W-1)/2
  sa=abs(A-B)
  sa=max(sa,abs(B-C),abs(A-C))
  ans=min(ans, sa)
#縦長パターン
for w in range(W):
  A=w*H
  if H%2==0:
    B=(W-w)*(H/2)
    C=(W-w)*(H/2)
  else:
    B=(W-w)*(H+1)/2
    C=(W-w)*(H-1)/2
  sa=abs(A-B)
  sa=max(sa,abs(B-C),abs(A-C))
  ans=min(ans, sa)

#均等パターン
  ans=min(ans,H,W)
print(int(ans))

Submission status: Accepted

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


def max_diff(list):
    l0 = list[0]
    l1 = list[1]
    l2 = list[2]
    max_diff = max([abs(l0 - l1), abs(l0 - l2), abs(l1 - l2)])
    return max_diff


def min_square(h, w):
    w3 = w // 3
    w2 = w // 2
    h3 = h // 3
    h2 = h // 2
    w_3 = [w3, w3 + 1, w3 + 2]
    w_2 = [w2, w2 + 1, w2 + 2]
    h_3 = [h3, h3 + 1, h3 + 2]
    h_2 = [h2, h2 + 1, h2 + 2]
    min_list = []
    for k in w_3:
        for l in h_2:
            if 0 < k < w and 0 < l < h:
                min_list.append(max_diff([h * k, l * (w - k), (h - l) * (w - k)]))
    for k in w_2:
        for l in h_3:
            if 0 < k < w and 0 < l < h:
                min_list.append(max_diff([w * l, k * (h - l), (w - k) * (h - l)]))
    for k in w_3:
        if 0 < k < w:
            min_list.append(max_diff([k * h, k * h, (w - 2 * k) * h]))
    for k in h_3:
        if 0 < k < h:
            min_list.append(max_diff([k * w, k * w, (h - 2 * k) * w]))

    return min(min_list)


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

Submission status: Accepted

Solution code:
h, w = [int(n) for n in input().split()]
i = min(h, w)
j = max(h, w)
area = i * j
if i % 3 == 0 or j % 3 == 0:
    print(0)
else:
    lst = []
    for r, s in [(i, j), (j, i)]:
        
        p = s // 3 + 1
        q = s // 3 
        a1 = r * p
        a2 = r * q
        b1 = r // 2 * (s - p)
        bb1 = (r // 2 - 1) * (s - p)
        b2 = r // 2 * (s - q)
        bb2 = (r // 2 - 1) * (s - q)
        c1 = (s - p) // 2 * r
        cc1 = ((s - p) // 2- 1) * r
        c2 = (s - q) // 2 * r
        cc2 = ((s - q) // 2 - 1) * r
        tup = [(a1, b1), (a2, b2), (a1, c1), (a2, c2),
               (a1, bb1), (a2, bb2), (a1, cc1), (a2, cc2)]
        lst.extend([abs(max(a, b, area - a - b) - min(a, b, area - a - b))
                    for a, b in tup])
    print(min(lst))

Submission status: Accepted

Solution code:

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

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

else:
    m = H * W
    for i in range(1,H+1):
        a = i * W
        b = (H-i) * (W//2)
        c = (H-i) * (W - W//2)
        if m > max(a,b,c)-min(a,b,c):
            m = max(a,b,c)-min(a,b,c)
    for i in range(1,W+1):
        a = i * H
        b = (W-i) * (H//2)
        c = (W-i) * (H - H//2)
        if m > max(a,b,c)-min(a,b,c):
            m = max(a,b,c)-min(a,b,c)
    if m > H:
        m = H
    if m > W:
        m = W
    print(m)

Submission status: Accepted

Solution code:
def div2(h, w):
    if h % 2 == 0 or w % 2 == 0:
        return [h * w // 2] * 2
    if h > w:
        h, w = w, h
    return [h * (w - 1) // 2, h * (w + 1) // 2]


def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    d1 = w // 3
    areas1 = sorted([h * d1] + div2(h, w - d1))
    ans1 = areas1[-1] - areas1[0]
    d1 += 1
    areas2 = sorted([h * d1] + div2(h, w - d1))
    ans2 = areas2[-1] - areas2[0]

    d2 = h // 3
    areas3 = sorted([d2 * w] + div2(h - d2, w))
    ans3 = areas3[-1] - areas3[0]
    d2 += 1
    areas4 = sorted([d2 * w] + div2(h - d2, w))
    ans4 = areas4[-1] - areas4[0]

    return min(ans1, ans2, ans3, ans4)


print(solve(*map(int, input().split())))

Submission status: Accepted

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

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

    print(ans)

def choco(h, w):
    i = 1
    min_ = float('inf')
    max_ = 4
    diff = float('inf')
    while i <= w / 2:
        w2 = w - i
        s1 = h * i
        s2 = h * (w2 // 2)
        s3 = h * ((w2 + 1) // 2)
        min_ = min(s1, s2, s3)
        max_ = max(s1, s2, s3)
        if max_ - min_ < diff:
            diff = max_ - min_

        s2 = h // 2 * w2
        s3 = (h + 1) // 2 * w2
        min_ = min(s1, s2, s3)
        max_ = max(s1, s2, s3)
        if max_ - min_ < diff:
            diff = max_ - min_

        i += 1

    return diff

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def parallel_divide(H, W):
    return 0 if W % 3 == 0 else H
 
def perpendicular_divide(H, W):
    if W % 2 == 0:
        return W // 2
    S1 = (H - 1) // 3 if H % 3 == 1 else (H + 1) // 3
    S2 = (W + 1) // 2 * (H - S1)
    S3 = (W - 1) // 2 * (H - S1)
    S1 = S1 * W
    return max(S1, S2, S3) - min(S1, S2, S3)
 
H, W = map(int, input().strip().split(' '))
print(min(parallel_divide(H, W), parallel_divide(W, H), perpendicular_divide(H, W), perpendicular_divide(W, H)))