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 sys

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

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

kai_1 = min(H,W)

def solve_2(a,b):
	w = a // 2
	s_l = (a-w) * b
	s_s = w * b
	s_r = 0

	tmp = s_l

	for i in range(b):
		s_r += a
		s_s -= w
		s_l -= (a-w)

		sa = max(s_r,s_s,s_l) - min(s_r,s_s,s_l)

		if tmp > sa:
			tmp = sa
			continue
		else:
			return tmp

kai_2 = solve_2(H,W)
kai_3 = solve_2(W,H)

print(min(kai_1,kai_2,kai_3))

Submission status: Accepted

Solution code:

def main():
    H, W = map(int, input().split())
    ans = float('inf')
    for h in range(1, H):
        S1 = h*W
        S2 = ((H-h)//2) * W
        S3 = ((H-h+1)//2) * W
        dif = max(S1, S2, S3) - min(S1, S2, S3)
        ans = min(ans, dif)
        S2 = (H-h) * (W//2)
        S3 = (H-h) * ((W+1)//2)
        dif = max(S1, S2, S3) - min(S1, S2, S3)
        ans = min(ans, dif)
    tmp = H
    H = W
    W = tmp
    for h in range(1, H):
        S1 = h*W
        S2 = ((H-h)//2) * W
        S3 = ((H-h+1)//2) * W
        dif = max(S1, S2, S3) - min(S1, S2, S3)
        ans = min(ans, dif)
        S2 = (H-h) * (W//2)
        S3 = (H-h) * ((W+1)//2)
        dif = max(S1, S2, S3) - min(S1, S2, S3)
        ans = min(ans, dif)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    if h % 3 == 0 or w % 3 == 0:
        print(0)
    else:
        mt = 10 ** 20
        for i in range(h):
            y = i * w
            x = (h - i) * (w // 2)
            z = h * w - x - y
            mt = min(mt, abs(max(x, y, z) - min(x, y, z)))

            x = (h - i) // 2 * w
            z = h * w - x - y
            mt = min(mt, abs(max(x, y, z) - min(x, y, z)))

        for i in range(w):
            y = i * h
            x = (w - i) * (h // 2)
            z = h * w - x - y
            mt = min(mt, abs(max(x, y, z) - min(x, y, z)))

            x = (w - i) // 2 * h
            z = h * w - x - y
            mt = min(mt, abs(max(x, y, z) - min(x, y, z)))

        print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    [H, W] = string_to_int(inputs[0])
    IDEAL_SIZE = H * W / 3

    def separate_first(SH, SW):
        most_closed_size = None
        most_closed_i = None
        for h in range(1, SH):
            tmp_size = h * SW
            if most_closed_size is None:
                most_closed_size = tmp_size
                most_closed_i = h
            else:
                most_closed_diff = abs(IDEAL_SIZE - most_closed_size)
                tmp_diff = abs(IDEAL_SIZE - tmp_size)

                if most_closed_diff > tmp_diff:
                    most_closed_size = tmp_size
                    most_closed_i = h

        return (most_closed_i, most_closed_size)

    def separate_second_row(start_h, SH, SW):
        second_i = (SH - start_h) // 2 + start_h
        second_s = (second_i - start_h) * SW
        third_s = (SH - second_i) * SW
        return (second_i, second_s, third_s)

    def separate_second_column(start_h, SH, SW):
        second_i = SW // 2
        second_s = (SH - start_h) * second_i
        third_s = (SH - start_h) * (SW - second_i)
        return (second_i, second_s, third_s)

    def max_diff(f_s, s_s, t_s):
        diff_s = []
        diff_s.append(abs(f_s - s_s))
        diff_s.append(abs(f_s - t_s))
        diff_s.append(abs(s_s - t_s))

        return max(diff_s)

    diffs = []
    if H == 1:
        f_i, f_s = separate_first(W, H)
        s_i, s_s, t_s = separate_second_row(f_i, W, H)
        diffs.append(max_diff(f_s, s_s, t_s))
    elif W == 1:
        f_i, f_s = separate_first(W, H)
        s_i, s_s, t_s = separate_second_row(f_i, W, H)
        diffs.append(max_diff(f_s, s_s, t_s))
    else:
        f_i, f_s = separate_first(H, W)
        s_i, s_s, t_s = separate_second_row(f_i, H, W)
        diffs.append(max_diff(f_s, s_s, t_s))

        f_i, f_s = separate_first(W, H)
        s_i, s_s, t_s = separate_second_row(f_i, W, H)
        diffs.append(max_diff(f_s, s_s, t_s))

        f_i, f_s = separate_first(H, W)
        s_i, s_s, t_s = separate_second_column(f_i, H, W)
        diffs.append(max_diff(f_s, s_s, t_s))

        f_i, f_s = separate_first(W, H)
        s_i, s_s, t_s = separate_second_column(f_i, W, H)
        diffs.append(max_diff(f_s, s_s, t_s))
    return min(diffs)


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

Solution code:
def pat1(H,W):
    if H % 3 == 0:
        return 0
    else:
        return W

def pat2(H,W):
    if W % 3 == 0:
        return 0
    else:
        return H

def pat3(H,W):
    h1 = H // 2
    h2 = H - h1
    ans = 10**15 
    for w in range(1,W//2+1):
        s1 = h1 * (W-w)
        s2 = h2 * (W-w)
        s3 = H*w
        min1 = min(s1,s2,s3)
        max1 = max(s1,s2,s3)
        ans = min(ans,max1-min1)
    return ans

def pat4(H,W):
    w1 = W // 2
    w2 = W - w1
    ans = 10**15
    for h in range(1,H//2+1):
        s1 = w1*(H-h)
        s2 = w2*(H-h)
        s3 = W*h
        min1 = min(s1,s2,s3)
        max1 = max(s1,s2,s3)
        ans = min(ans,max1-min1)
    return ans

H,W = map(int,input().split())
ans = 10**15
ans = min(ans,pat1(H,W))
ans = min(ans,pat2(H,W))
ans = min(ans,pat3(H,W))
ans = min(ans,pat4(H,W))

print(ans)

Submission status: Accepted

Solution code:
H, W = list(map(int,input().split()))
ans = H*W
h = H
w = W
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*W
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
h = W
w = H
for i in range(h//3,h//2+1):
    p1 = i*w
    for j in range((h-i)//2-1,(h-i)//2+1):
        p2 = (h-i-j)*H
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
    for j in range(w//2-1,w//2+1):
        p2 = (h-i)*(w-j)
        ans = min(ans, max(p1,p2,h*w-p1-p2)-min(p1,p2,h*w-p1-p2))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def a(n,m):
	l1=n//3*2+1
	l2=n-l1
	l3=m//2
	l4=m-l3
	A=[l2*m,l1*l3,l1*l4]
	r=max(A)-min(A)
	if n>3:
		l5=l1//2
		l6=l1-l5
		B=[l2*m,l5*m,l6*m]
		r=min(r,max(B)-min(B))
	return r
h,w=map(int,input().split())
if h%3==0 or w%3==0:
	print(0)
else:
	print(min(a(h,w),a(w,h)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

h, w = [int(x) for x in input().split()]

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

if h % 3 == 1:
    d = h // 3 
else:
    d = h // 3 + 1
block = [w * d, (h-d) * (w // 2), (h-d) * (w - w // 2)]
res1 = max(block) - min(block)
block = [w * d, w * d, w * (h - d * 2)]
res2 = max(block) - min(block)

if w % 3 == 1:
    d = w // 3 
else:
    d = w // 3 + 1
block = [h * d, (w-d) * (h // 2), (w-d) * (h - h // 2)]
res3 = max(block) - min(block)
block = [h * d, h * d, h * (w - d * 2)]
res4 = max(block) - min(block)

print(min(res1, res2, res3, res4))

Submission status: Accepted

Solution code:
INF = float('inf')


def f(H, W):
    return min(f1(H, W), f1(W, H))


def f1(H, W):
    result = INF
    for h in range(1, H):
        t = [h * W] + f2(H - h, W)
        t.sort()
        if abs(t[0] - t[2]) < result:
            result = abs(t[0] - t[2])
        t = [h * W] + f2(W, H - h)
        t.sort()
        if abs(t[0] - t[2]) < result:
            result = abs(t[0] - t[2])
    return result


def f2(H, W):
    if H < 2:
        return [-INF, INF]
    h = H // 2
    return [h * W, (H - h) * W]


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

print(f(H, W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
 
if H*W %3 ==0:
    print(0)
    exit()
 
diff_list = [W,H]
 
#縦→横
split1 = [W//3, W//3 + 1]
split2 = [H//2, H//2 +1]
 
for w in split1:
    for h in split2:
        temp = [H*w, h*(W-w), (H-h)*(W-w)]
        diff_list.append(abs(max(temp)-min(temp)))
 
#横→縦
if H != W:
    split1 = [H//3, H//3 + 1]
    split2 = [W//2, W//2 + 1]
 
    for h in split1:
        for w in split2:
            temp = [h*W, (H-h)*w, (H-h)*(W-w)]
            diff_list.append(abs(max(temp)-min(temp)))
 
# print(diff_list)
print(min(diff_list))

Submission status: Accepted

Solution code:

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


if h%3==0 or w%3==0:
    print(0)
else:
    l=[]
    #縦割り
    l.append(h)
    #横割り
    l.append(w)
    #半縦割り
    for i in range(1,w):
        x,y,z=sorted([i*h,(w-i)*(h//2),(w-i)*(h-h//2)])
        l.append(z-x)
    #半横割り
    for i in range(1,h):
        x,y,z=sorted([i*w,(h-i)*(w//2),(h-i)*(w-w//2)])
        l.append(z-x)
    print(min(l))

Submission status: Accepted

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

ans=h*w

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


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

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

print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=min((H%3>0)*W,(W%3>0)*H)
A=[0]*3
A[0]=H//3*W
A[1]=(H-H//3)*(W//2)
A[2]=H*W-A[0]-A[1]
A.sort()
ans=min(ans,A[2]-A[0])
A[0]=(H//3+1)*W
A[1]=(H-H//3-1)*(W//2)
A[2]=H*W-A[0]-A[1]
A.sort()
ans=min(ans,A[2]-A[0])
H,W=W,H
A[0]=H//3*W
A[1]=(H-H//3)*(W//2)
A[2]=H*W-A[0]-A[1]
A.sort()
ans=min(ans,A[2]-A[0])
A[0]=(H//3+1)*W
A[1]=(H-H//3-1)*(W//2)
A[2]=H*W-A[0]-A[1]
A.sort()
ans=min(ans,A[2]-A[0])
print(ans)

Submission status: Accepted

Solution code:
def func(H,W):
    if H % 3 == 0:
        return 0

    H_3 = int(H/3)
    S1 = H_3 * W
    S2 = (H - H_3) * int(W/2)
    S3 = H * W - S1 - S2 
    
    res1 = max(S1, S2, S3) - min(S1, S2, S3)
    
    H_3_1 = int(H/3) + 1
    S1 = H_3_1 * W
    S2 = (H - H_3_1) * int(W/2)
    S3 = H * W - S1 - S2 
    
    res2 = max(S1, S2, S3) - min(S1, S2, S3)
    
    return min(res1 ,res2)
H, W = list(map(int, input().split()))
print(min(func(H,W), func(W,H), H, W))

Submission status: Accepted

Solution code:
# ABC062 C - Chocolate Bar
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

h,w = nm()

if h==2 and w==2:
    print(1)
    exit()

s = h*w
s1 = 0
s2 = 0
s3 = 0
wm = w//2
hm = h//2
s_max = 0
s_min = 0
ans_1 = 10**10
ans_2 = 10**10
ans_3 = 10**10
ans_4 = 10**10

for i in range(1,h-1):
    s1 = i*w
    s2 = ((h-i)//2)*w
    s3 = s-s1-s2
    s_max = max(s1,s2,s3)
    s_min = min(s1,s2,s3)
    ans_1 = min(ans_1,s_max-s_min)

for i in range(1,h-1):
    s1 = i*w
    s2 = (h-i)*wm
    s3 = s-s1-s2
    s_max = max(s1,s2,s3)
    s_min = min(s1,s2,s3)
    ans_2 = min(ans_2,s_max-s_min)

for i in range(1,w-1):
    s1 = i*h
    s2 = ((w-i)//2)*h
    s3 = s-s1-s2
    s_max = max(s1,s2,s3)
    s_min = min(s1,s2,s3)
    ans_3 = min(ans_3,s_max-s_min)

for i in range(1,w-1):
    s1 = i*h
    s2 = (w-i)*hm
    s3 = s-s1-s2
    s_max = max(s1,s2,s3)
    s_min = min(s1,s2,s3)
    ans_4 = min(ans_4,s_max-s_min)

print(min(ans_1,ans_2,ans_3,ans_4))

Submission status: Accepted

Solution code:
def func(H,W):
    area = H * W

    half_H = int(H/2)
    half_W = int(W/2)  
    
    res = 10000000
    
    # よこ
    # T
    for x in range(1,W):
        S1 = H * x
        S2_T = (W - x) * half_H
        S3_T = area - S1 - S2_T
        
        S2_2 = H * int((W - x)/2)
        S3_2 = area - S1 - S2_2
        
        tmpres_T = max(S1, S2_T, S3_T) - min(S1, S2_T, S3_T)
        tmpres_2 = max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2)
        
        if tmpres_T < res:
            res = tmpres_T
        if tmpres_2 < res:
            res = tmpres_2
    # たて
    # T
    for y in range(1,H):
        S1 = W * y
        S2_T = (H - y) * half_W
        S3_T = area - S1 - S2_T
        
        S2_2 = W * int((H - y)/2)
        S3_2 = area - S1 - S2_2
        
        tmpres_T = max(S1, S2_T, S3_T) - min(S1, S2_T, S3_T)
        tmpres_2 = max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2)
        
        if tmpres_T < res:
            res = tmpres_T
        if tmpres_2 < res:
            res = tmpres_2
    
    return res

H, W = list(map(int, input().split()))
print(func(H,W))

Submission status: Accepted

Solution code:
def f(Hn, Wn):
    ret = float('inf')
    for Wi in range(1, Wn):
        h = Hn // 2
        w = Wn - Wi
        Sn = Wi * Hn, w * h, w * (Hn - h)
        ret = min(ret, max(Sn) - min(Sn))
        w //= 2
        Sn = Wi * Hn, w * Hn, (Wn - Wi - w) * Hn
        ret = min(ret, max(Sn) - min(Sn))
    return ret


def main():
    H, W = map(int, input().split())
    ans = f(H, W)
    if not ans:
        print(ans)
        return
    ans = min(ans, f(W, H))
    if not ans:
        print(ans)
        return
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
a = W%3
if a==0:
    s1 = 0
else:
    s1 = H
a = H%3
if a==0:
    s2 = 0
else:
    s2 = W
s3 = H*W
for i in range(1,W):
    a = max(i*H,(H-H//2)*(W-i))
    b = min(i*H,(H//2)*(W-i))
    s3 = min(s3,a-b)
s4 = H*W
for i in range(1,H):
    a = max(i*W,(W-W//2)*(H-i))
    b = min(i*W,(W//2)*(H-i))
    s4 = min(s4,a-b)
print(min(s1,s2,s3,s4))

Submission status: Accepted

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

mind = float('inf')

for i in range(1,h):
  d = max(abs(w*i-(w//2)*(h-i)),abs(w*i+(-w//2)*(h-i)),(h-i)*bool(w%2))
  mind = min(mind,d)

for i in range(1,w):
  d = max(abs(h*i-(h//2)*(w-i)),abs(h*i+(-h//2)*(w-i)),(w-i)*bool(h%2))
  mind = min(mind,d)

mind = min(mind,min(h,w)*bool(max(h,w)%3)*bool((h*w)%3))

print(mind)

Submission status: Accepted

Solution code:
def sp(n):
  a = n // 3
  b = (n - a) // 2
  c = n -a -b
  return a,b,c

def ceil(x, y):
  return (x -1) // y + 1

def tatedake_diff(h, w):
  a,b,c = sp(h)
  s1 = (c-a) * w
  a,b,c = sp(w)
  s2 = (c-a) * h
  return min(s1, s2)

def tateyoko_diff(h, w):
  a,b,c = sp(h)
  s1 = (c * w)
  s2 = (h - c) * (w // 2)
  s3 = (h - c) * ceil(w, 2)
  r1 = max(s1,s2,s3) - min(s1,s2,s3)
  s1 = (a * w)
  s2 = (h - a) * (w // 2)
  s3 = (h - a) * ceil(w, 2)
  r2 = max(s1,s2,s3) - min(s1,s2,s3)
  return min(r1,r2)
  
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
  ans = 0
else:
  ans = min(tatedake_diff(H, W), tateyoko_diff(H, W), tateyoko_diff(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:
    ans=float('inf')
    for i in range(1,h):
        c=max(i*(w//2),i*(w-w//2),(h-i)*w)-min(i*(w//2),i*(w-w//2),(h-i)*w)
        if ans>c:
            ans=c
        #print(ans)
    for i in range(1,w):
        d=max(i*(h//2),i*(h-h//2),(w-i)*h)-min(i*(h//2),i*(h-h//2),(w-i)*h)
        if ans>d:
            ans=d
        #print(ans)
    print(min(ans,h,w))

Submission status: Accepted

Solution code:
from math import ceil


# 川の字に分割
def river(x, y):
    diff = ceil(x / 3) - x // 3
    return diff * y


# T字に分割
def t(x, y):
    def f(uy):
        dy = y - uy
        lx = x // 2
        rx = x - lx
        us = x * uy
        ls = lx * dy
        rs = rx * dy
        return max(us, ls, rs) - min(us, ls, rs)

    return min(f(y // 3), f(ceil(y / 3)))


def solve(h, w):
    return min(river(h, w), river(w, h), t(h, w), t(w, h))


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    h, w = map(int, input().split())
    p = [h//2+w//3+1, h//3+w//2+1, h, w]
    if h % 3 == 0 or w % 3 == 0:
        p += [0]
    if h % 2 == 0:
        p += [h//2]
    if w % 2 == 0:
        p += [w//2]
    print(min(p))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# C - Chocolate Bar

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

def ans_every_h1(H,W):
    piece = [0]*3
    for h1 in range(1,H):
        piece[0] = h1*W
        piece[1] = ((H - h1)//2) * W
        piece[2] = H*W - piece[0] - piece[1]
        ans_list.append(max(piece) - min(piece))
        
        piece[1] = (H - h1) * (W//2)
        piece[2] = H*W - piece[0] - piece[1]
        ans_list.append(max(piece) - min(piece))

if H%3 == 0 or W%3 == 0:
    print(0)
else:
    ans_list = []
    ans_every_h1(H,W)
    ans_every_h1(W,H)
    print(min(ans_list))

Submission status: Accepted

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

s1 = (h // 3) * w
s2 = (h - (h // 3)) * (w // 2)
s3 = h * w - s1 - s2
diff_sh1 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = (h // 3 + 1) * w
s2 = (h - (h // 3 + 1)) * (w // 2)
s3 = h * w - s1 - s2
diff_sh2 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = (h // 3) * w
s2 = ((h - (h // 3)) // 2) * w
s3 = h * w - s1 - s2
diff_sh3 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = (h // 3 + 1) * w
s2 = ((h - (h // 3 + 1)) // 2) * w
s3 = h * w - s1 - s2
diff_sh4 = max(s1, s2, s3) - min(s1, s2, s3)


s1 = h * (w // 3)
s2 = (h // 2) * (w - (w // 3))
s3 = h * w - s1 - s2
diff_sw1 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = h * (w // 3 + 1)
s2 = (h // 2) * (w - (w // 3 + 1))
s3 = h * w - s1 - s2
diff_sw2 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = h * (w // 3)
s2 = h * ((w - (w // 3)) // 2)
s3 = h * w - s1 - s2
diff_sw3 = max(s1, s2, s3) - min(s1, s2, s3)

s1 = h * (w // 3 + 1)
s2 = h * ((w - (w // 3 + 1)) // 2)
s3 = h * w - s1 - s2
diff_sw4 = max(s1, s2, s3) - min(s1, s2, s3)

min_sh = min(diff_sh1, diff_sh2, diff_sh3, diff_sh4)
min_sw = min(diff_sw1, diff_sw2, diff_sw3, diff_sw4)
print(min(min_sh, min_sw))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=10000000000000
for i in range(1,n):
    a=i*m
    nk=n-i
    if nk%2==0:
        b=m*(nk//2)
        ans=min(ans,abs(a-b))
    elif nk>1:
        b=m*((nk+1)//2)
        c=m*((nk-1)//2)
        ans=min(ans,max(a,b,c)-min(a,b,c))
    if m%2==0:
        b=nk*m//2
        ans=min(ans,abs(a-b))
    elif m>1:
        b=nk*(m+1)//2
        c=nk*(m-1)//2
        ans=min(ans,max(a,b,c)-min(a,b,c))

for i in range(1,m):
    a=i*n
    nk=m-i
    if nk%2==0:
        b=n*(nk//2)
        ans=min(ans,abs(a-b))
    elif nk>1:
        b=n*((nk+1)//2)
        c=n*((nk-1)//2)
        ans=min(ans,max(a,b,c)-min(a,b,c))
    if n%2==0:
        b=nk*n//2
        ans=min(ans,abs(a-b))
    elif n>1:
        b=nk*(n+1)//2
        c=nk*(n-1)//2
        ans=min(ans,max(a,b,c)-min(a,b,c))
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=h*w
  v=w//2
  for i in range(1,h):
    a=i*w
    y=(h-i)//2
    z=h-i-y
    b=y*w
    c=z*w
    d=(h-i)*v
    e=(h-i)*(w-v)
    ans=min(ans,max(a,b,c)-min(a,b,c),max(a,d,e)-min(a,d,e))
  v=h//2
  for i in range(1,w):
    a=i*h
    y=(w-i)//2
    z=w-i-y
    b=y*h
    c=z*h
    d=(w-i)*v
    e=(w-i)*(h-v)
    ans=min(ans,max(a,b,c)-min(a,b,c),max(a,d,e)-min(a,d,e))
  print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:

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

ans = min(H, W)


if H % 3 == 0 or W % 3 == 0:
    ans = 0
    
for ha in range(H//3, H//3+3):
    Sa = ha * W
    
    ## 横に分割
    hb = (H - ha)//2
    hc = H - ha - hb
    Sb = hb * W
    Sc = hc * W
    ans = min(ans, max(Sa, Sb, Sc) - min(Sa, Sb, Sc))
    
    ## 縦に分割
    wb = W//2
    wc = W - wb
    Sb = (H - ha) * wb
    Sc = (H - ha) * wc
    ans = min(ans, max(Sa, Sb, Sc) - min(Sa, Sb, Sc))

for wa in range(W//3, W//3+3):
    Sa = H * wa
    
    ## 横に分割
    hb = H//2
    hc = H - hb
    Sb = hb * (W - wa)
    Sc = hc * (W - wa)
    ans = min(ans, max(Sa, Sb, Sc) - min(Sa, Sb, Sc))
    
    ## 縦に分割
    wb = (W - wa)//2
    wc = W - wa - wb
    Sb = H * wb
    Sc = H * wc
    ans = min(ans, max(Sa, Sb, Sc) - min(Sa, Sb, Sc))

print(ans)

Submission status: Accepted

Solution code:
def minimize(H, W):
    ans = float('inf')
    for h in range(1, H):
        sa = h * W
        sb = (H - h) * (W // 2)
        sc = (H - h) * (W - W // 2)
        smax = max(sa, sb, sc)
        smin = min(sa, sb, sc)
        ans = min(ans, smax - smin)

        sb = W * ((H - h) // 2)
        sc = W * (H - h - (H - h) // 2)
        smax = max(sa, sb, sc)
        smin = min(sa, sb, sc)
        ans = min(ans, smax - smin)
    return ans

H, W = tuple(map(int, input().split()))
ans1 = minimize(H, W)
ans2 = minimize(W, H)
print(min(ans1, ans2))

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:
H, W = map(int, input().split())
ans = []

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

s1 = [H * (W // 3), H // 2 * (W - W // 3), (H // 2 + H % 2) * (W - W // 3)]
s2 = [H * (W // 3 + 1), H // 2 * (W - W // 3 - 1), (H // 2 + H % 2) * (W - W // 3 - 1)]

ans.append(min(max(s1) - min(s1), max(s2) - min(s2)))

H, W = W, H

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

s1 = [H * (W // 3), H // 2 * (W - W // 3), (H // 2 + H % 2) * (W - W // 3)]
s2 = [H * (W // 3 + 1), H // 2 * (W - W // 3 - 1), (H // 2 + H % 2) * (W - W // 3 - 1)]

ans.append(min(max(s1) - min(s1), max(s2) - min(s2)))

print(min(ans))

Submission status: Accepted

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

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

s1 = [H * (W // 3), H // 2 * (W - W // 3), (H // 2 + H % 2) * (W - W // 3)]
s2 = [H * (W // 3 + 1), H // 2 * (W - W // 3 - 1), (H // 2 + H % 2) * (W - W // 3 - 1)]

ans.append(min(max(s1) - min(s1), max(s2) - min(s2)))

H, W = W, H

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

s1 = [H * (W // 3), H // 2 * (W - W // 3), (H // 2 + H % 2) * (W - W // 3)]
s2 = [H * (W // 3 + 1), H // 2 * (W - W // 3 - 1), (H // 2 + H % 2) * (W - W // 3 - 1)]

ans.append(min(max(s1) - min(s1), max(s2) - min(s2)))

print(min(ans))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = float("Inf")
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
for i in range(1,h):
    a = (h-i)*(w//2)
    b = (h-i)*-(-w//2)
    c = ((h-i)//2) * w
    d = -(-(h-i)//2) * w
    ans = min(ans,max(i*w,a,b)-min(i*w,a,b))
    ans = min(ans,max(i*w,c,d)-min(i*w,c,d))
for i in range(1,w):
    a = (w-i)*(h//2)
    b = (w-i)*(h-(h//2))
    c = ((w-i)//2) * h
    d = -(-(w-i)//2) * h
    ans = min(ans,max(i*h,a,b)-min(i*h,a,b))
    ans = min(ans,max(i*h,c,d)-min(i*h,c,d))
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = float("Inf")
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
for i in range(1,h):
    a = (h-i)*(w//2)
    b = (h-i)*-(-w//2)
    ans = min(ans,abs(max(i*w,a,b)-min(i*w,a,b)))
for i in range(1,w):
    a = (w-i)*(h//2)
    b = (w-i)*-(-h//2)
    ans = min(ans,abs(max(i*h,a,b)-min(i*h,a,b)))
print(min(ans,h,w))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
res = min(H, W)
h = round(H / 3)
w = W // 2
s1 = h * W
s2 = (H-h) * w
s3 = (H-h) * (W-w)
res = min(res, max(s1, s2, s3) - min(s1, s2, s3))
w = round(W / 3)
h = H // 2
s1 = w * H
s2 = (W-w) * h
s3 = (W-w) * (H-h)
res = min(res, max(s1, s2, s3) - min(s1, s2, s3))
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)

Submission status: Accepted

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    for h in range(1,H):
        A = h * W
        B = (H - h) * -(-W // 2)
        C = (H - h) * (W // 2) 
        ans = min(ans, max(A,B,C)-min(A,B,C))

    for w in range(1,W):
        A = w * H
        B = (W - w) * -(-H // 2)
        C = (W - w) * (H // 2) 
        ans = min(ans, max(A,B,C)-min(A,B,C))
    print(min(ans, H, W))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
  a=0
else:
  def func(x,y):
    a=10**5
    for i in range(1,x//3+2):
      s=i*y
      t=((x-i)//2)*y
      b=max(s,t,x*y-s-t)-min(s,t,x*y-s-t)
      t=(y//2)*(x-i)
      a=min(a,b,max(s,t,x*y-s-t)-min(s,t,x*y-s-t))
    return a
  a=min(func(w,h),func(h,w))
print(a)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
if h%3!=0 and w%3!=0:
    ansh=h*w
    for j in range(1,h):
        area1=w*j
        number=w//2
        area2=(h-j)*number
        area3=(h-j)*(w-number)
        check=max(abs(area1-area2),abs(area1-area3),abs(area2-area3))
        if check<ansh:
            ansh=check
        else:
            continue  
    answ=w*h
    for j in range(1,w):
        area1=h*j
        number=h//2
        area2=(w-j)*number
        area3=(w-j)*(h-number)
        check=max(abs(area1-area2),abs(area1-area3),abs(area2-area3))
        if check<answ:
            answ=check
        else:
             continue
    print(min(ansh,answ,w,h))

Submission status: Accepted

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

ds = []

for i in range(1, h):
  s1 = w*i
  s2 = (h-i)*(w//2)
  s3 = (h-i)*(w-w//2)
  d1 = max(s1, s2, s3) - min(s1, s2, s3)
  
  s1 = w*i
  s2 = w*((h-i)//2)
  s3 = w*(h-(h-i)//2-i)
  d2 = max(s1, s2, s3) - min(s1, s2, s3)
  
  if i == h-1:
    d = d1
  else:
    d = min(d1, d2)
  ds.append(d)

for i in range(1, w):
  s1 = h*i
  s2 = (w-i)*(h//2)
  s3 = (w-i)*(h-h//2)
  d1 = max(s1, s2, s3) - min(s1, s2, s3)
  
  s1 = h*i
  s2 = h*((w-i)//2)
  s3 = h*(w-(w-i)//2-i)
  d2 = max(s1, s2, s3) - min(s1, s2, s3)
  
  if i == w-1:
    d = d1
  else:
    d = min(d1, d2)
  ds.append(d)
  
print(min(ds))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    if h%3==0 or w%3==0:
        print(0)
        return
    ans=INF
    # hをtrisect, wをbisect
    a=(h//3)*w
    b=(h-h//3)*(w//2)
    c=h*w-a-b
    ans=min(ans,max(a,b,c)-min(a,b,c))
    a=(h//3+1)*w
    b=(h-h//3-1)*(w//2)
    c=h*w-a-b
    ans=min(ans,max(a,b,c)-min(a,b,c))
    # hをbisect, wをtrisect
    a=(w//3)*h
    b=(w-w//3)*(h//2)
    c=h*w-a-b
    ans=min(ans,max(a,b,c)-min(a,b,c))
    a=(w//3+1)*h
    b=(w-w//3-1)*(h//2)
    c=h*w-a-b
    ans=min(ans,max(a,b,c)-min(a,b,c))
    # hをtrisect
    print(min(ans,h,w))
resolve()

Submission status: Accepted

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

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

Submission status: Accepted

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


def calc(a, b):
    return min([
        b,
        max([
            abs(a // 3 * b - (a - a // 3) * (b // 2)),
            abs(a // 3 * b - (a - a // 3) * (b // 2 + b % 2)),
            (a - a // 3) * (b % 2),
        ]),
        max([
            abs((a // 3 + 1) * b - (a - a // 3 - 1) * (b // 2)),
            abs((a // 3 + 1) * b - (a - a // 3 - 1) * (b // 2 + b % 2)),
            (a - a // 3 - 1) * (b % 2),
        ]),
    ])


if h * w % 3 == 0:
    print(0)
else:
    print(min([calc(h, w), calc(w, h)]))

Submission status: Accepted

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

if h % 3 == 0 or h % 3 == 0:
    print(0)
    exit()
for i in range(1,w):
    H1, H2= h//2, -(-h//2)
    check = max(h*i,H2*(w-i),H1*(w-i))
    check2 = min(h*i,H1*(w-i),H2*(w-i))
    ans = min(ans,abs(check-check2))
for i in range(1,h):
    w1,w2 = w//2, -(-w//2)
    check = max(w*i,w1*(h-i),w2*(h-i))
    check2 = min(w*i,w1*(h-i),w2*(h-i))
    ans = min(ans,abs(check-check2))
print(min(ans,h,w))