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: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
h,w = map(int,input().split())
if w % 3 == 0 or h % 3 == 0:
    print(0)
elif h % 2 == 1 and w % 2 == 0:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))
elif h % 2 == 0 and w % 2 == 1:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))
elif h % 2 == 1 and w % 2 == 1:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))
    
else:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h // 3) * w
    smin = (h - (h//3)) * (w//2)
    arr.append(abs(smax - smin))
    smax = (w//3) * h
    smin = (w - (w//3)) * (h//2)    
    arr.append(abs(smax - smin))
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
if h%3 == 0 or w%3 == 0:
  print(0)
else:
  ret = h*w
  for hi in range(max(1,h//3-10),min(h,h//3+10)):
    s1 = hi*w
    for wi in range(max(1,w//2-10),min(w,w//2+10)):
      s2 = (h-hi)*wi
      s3 = (h-hi)*(w-wi)
      d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
      ret = min(ret,d)
  for wi in range(max(1,w//3-10),min(w,w//3+10)):
    s1 = wi*h
    for hi in range(max(1,h//2-10),min(h,h//2+10)):
      s2 = (w-wi)*hi
      s3 = (w-wi)*(h-hi)
      d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
      ret = min(ret,d)
  print(ret)

Submission status: Wrong Answer

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

def w_div_3(H, W):
    w = W // 3
    if w == 0:
        return 10000000000
    rw = W - 2 * w
    return (rw - w) * H

def h_div_3(H, W):
    h = H // 3
    if h == 0:
        return 10000000000
    rh = H - 2 * h
    return (rh - h) * W

def w_div_h_div(H, W):
    min_diff = 10000000000
    for w in range(1, W):
        a1 = w * H
        a2 = (W - w) * (H // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

def h_div_w_div(H, W):
    min_diff = 10000000000
    for h in range(1, H):
        a1 = h * W
        a2 = (H - h) * (W // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(min(w_div_3(H, W), h_div_3(H, W), w_div_h_div(H, W), h_div_w_div(H, W)))

Submission status: Wrong Answer

Solution code:
x, y = map(int, raw_input().split())
if x < y:
	x, y = y, x

if x % 3 == 0 or y % 3 == 0:
	print 0
else:
	m = 1000000
	for i in range(1, x):
		j = y / 2
		s1 = y * i
		s2 = (x - i) * j
		s3 = (x - i) * (y - j)
		l = [s1, s2, s3]
		l.sort()
		if l[-1] - l[0] < m:
			m = l[-1] - l[0]
			# ix = i
			# ij = j
	print m

Submission status: Wrong Answer

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

if (H*W)%3==0:
    print 0
else:
    s_min=float('inf')
    for h in range(1,H+1):
        w=(H*W/3)/h
        for _ in range(2):
            v1=(h*w,(W-w)*h,W*(H-h))
            v2=(h*w,(W-w)*H,w*(H-h))
            s=min(max(v1)-min(v1),max(v2)-min(v2))
            if s_min>s:
                s_min=s
            w+=1

    print s_min

Submission status: Wrong Answer

Solution code:
def solve(H,W,d=3.0):
    ave = int(((H*W)/d+0.5))
    h = 0
    w = 0
    for i in xrange(H):
        div = abs((i+1)*W-ave)
        bdiv = abs((h+1)*W-ave)
        if div <= bdiv:
            h = i
        else:
            break
    for i in xrange(W):
        div = abs((i+1)*H-ave)
        bdiv = abs((w+1)*H-ave)
        if div <= bdiv:
            w = i
        else:
            break
    hdiv = abs((h+1)*W-ave)
    wdiv = abs((w+1)*H-ave)
    if hdiv<wdiv:
        return (h+1,0)
    else:
        return (0,w+1)

H,W = map(int,raw_input().split(' '))
s_ = H*W
S = []
a = solve(H,W)
s = a[0]*W + a[1]*H
S.append(s)
H -= a[0]
W -= a[1]
b= solve(H,W,2.0)
s = b[0]*W + b[1]*H
S.append(s)
S.append((s_-sum(S)))
print max(S)-min(S)

Submission status: Wrong Answer

Solution code:
def splt(H, W, S, den):
    S_1, H_1, W_1 = 0, 0, 0
    mini = 10**11

    for h in range(1, H):
        if abs(S/den - h*W) < mini:
            H_1 = H - h
            W_1 = W
            mini = abs(S/den - h*W)

    for w in range(1, W):
        if abs(S/den - w*H) < mini:
            H_1 = H
            W_1 = W - w
            mini = abs(S/den - w*H)

    return H_1, W_1, S - H_1*W_1


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

S = H*W

H_1, W_1, S_1 = splt(H, W, S, 3)
H_2, W_2, S_2 = splt(H_1, W_1, S - S_1, 2)
S_3 = H_2 * W_2

df = [abs(S_1-S_2), abs(S_2-S_3), abs(S_3-S_1)]

print(max(df))

Submission status: Wrong Answer

Solution code:
def rren(): return list(map(int, input().split()))


H, W = rren()
if(H % 3 == 0 or W % 3 == 0):
    print(0)
else:
    lis = []
    ans = 114514810
    for i in range(H-1):
        a = H - i
        b = W - a
        c = H // 2
        lis = [H*a, b*c, (H-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    for i in range(W-1):
        a = W - i
        b = H - a
        c = W // 2
        lis = [W*a, b*c, (W-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    ans = min(ans, abs((W//3) - (W-(W//3)*2))*H)
    ans = min(ans, abs(H//3 - (H-(H//3)*2))*W)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
h,w = map(int,input().split())
if w % 3 == 0 or h % 3 == 0:
    print(0)
elif h % 2 == 1 and w % 2 == 0:
    smax = (h // 3 + 1) * w
    smin = (h-(h//3 + 1)) * (w//2)
    print(smax-smin)
elif h % 2 == 0 and w % 2 == 1:
    smax = (w // 3 + 1) * h
    smin = (w-(w//3 + 1)) * (h//2)
    print(smax-smin)
elif h % 2 == 1 and w % 2 == 1:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))
    
else:
    arr = []
    smax = (h // 3 + 1) * w
    smin = (h - (h//3 + 1)) * (w//2)
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w - (w//3 + 1)) * (h//2)
    arr.append(smax - smin)
    
    smax = (h // 3) * w
    smin = (h - (h//3)) * (w//2)
    arr.append(abs(smax - smin))
    smax = (w//3) * h
    smin = (w - (w//3)) * (h//2)    
    arr.append(abs(smax - smin))
    
    smax = (h//3 + 1) * w
    smin = (h//3) * w
    arr.append(smax - smin)
    smax = (w//3 + 1) * h
    smin = (w//3) * h
    arr.append(smax - smin)    
    print(min(arr))

Submission status: Wrong Answer

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

def w_div_3(H, W):
    w = W // 3
    if w == 0:
        return 10000000000
    rw = W - 2 * w
    return (rw - w) * H

def h_div_3(H, W):
    h = H // 3
    if h == 0:
        return 10000000000
    rh = H - 2 * h
    return (rh - h) * W

def w_div_h_div(H, W):
    min_diff = 10000000000
    for w in range(1, W):
        a1 = w * H
        a2 = (W - w) * (H // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

def h_div_w_div(H, W):
    min_diff = 10000000000
    for h in range(1, H):
        a1 = h * W
        a2 = (H - h) * (W // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(min(w_div_3(H, W), h_div_3(H, W), w_div_h_div(H, W), h_div_w_div(W, H)))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
if h%3 == 0 or w%3 == 0:
  print(0)
else:
  h1 = h//3
  h2 = h1+1
  w1 = w//3
  w2 = w1+1
  ret = h*w
  for hi in {h1,h2}:
    s1 = hi*w
    s2 = (h-hi)*(w//2)
    s3 = (h-hi)*(w-w//2)
    d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
    ret = min(ret,d)
  for wi in {w1,w2}:
    s1 = wi*h
    s2 = (w-wi)*(h//2)
    s3 = (w-wi)*(h-h//2)
    d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
    ret = min(ret,d)
  print(ret)

Submission status: Wrong Answer

Solution code:
x, y = map(int, raw_input().split())
if x < y:
	x, y = y, x

if x % 3 == 0 or y % 3 == 0:
	print 0
else:
	i = (x + 1) / 3
	j = y / 2
	s1 = y * i
	s2 = (x - i) * j
	s3 = (x - i) * (y - j)
	l = [s1, s2, s3]
	l.sort()
	print l[-1] - l[0]

Submission status: Wrong Answer

Solution code:
def rren(): return list(map(int, input().split()))


H, W = rren()
if(H % 3 == 0 or W % 3 == 0):
    print(0)
else:
    lis = []
    ans = 114514810
    for i in range(H-1):
        a = H - i
        b = W - a
        c = H // 2
        lis = [H*a, b*c, (H-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    for i in range(W-1):
        a = W - i
        b = H - a
        c = W // 2
        lis = [W*a, b*c, (W-c)*b]
        ans = min(ans, max(lis) - min(lis))
        lis.clear()
    print(ans)

Submission status: Wrong Answer

Solution code:
def rren(): return list(map(int, input().split()))


H, W = rren()
if(H % 3 == 0 or W % 3 == 0):
    print(0)
else:
    lis = []
    a = H // 3
    b = W - a
    c = H // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = max(lis) - min(lis)
    lis.clear()
    a = W // 3
    b = H - a
    c = W // 2
    lis = [W*a, b*c, (W-c)*b]
    ans = min(ans, max(lis) - min(lis))
    lis.clear()
    a = H // 3 + 1
    b = W - a
    c = H // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = max(lis) - min(lis)
    lis.clear()
    a = W // 3 + 1
    b = H - a
    c = W // 2
    lis = [W*a, b*c, (W-c)*b]
    ans = min(ans, max(lis) - min(lis))
    print(ans)

Submission status: Wrong Answer

Solution code:
def rren(): return list(map(int, input().split()))


H, W = rren()
if(H % 3 == 0 or W % 3 == 0):
    print(0)
else:
    lis = []
    a = H // 3
    b = W - a
    c = H // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = max(lis) - min(lis)
    lis.clear()
    a = W // 3
    b = H - a
    c = W // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = min(ans, max(lis) - min(lis))
    lis.clear()
    a = H // 3 + 1
    b = W - a
    c = H // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = max(lis) - min(lis)
    lis.clear()
    a = W // 3 + 1
    b = H - a
    c = W // 2
    lis = [H*a, b*c, (H-c)*b]
    ans = min(ans, max(lis) - min(lis))
    print(ans)

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in raw_input().split()]
def f(h, w):
    hw = h * w
    a = h / 2 * w
    _hw = hw - a
    b = _hw / 2 - _hw %2
    c = _hw - b
    mx = max(a, b, c)
    mn = min(a, b, c)
    return mx - mn
print(min(f(h, w), f(w, h)))

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    ans = 10 ** 10
    m1, m2 = m // 2, m - m // 2
    for i in range(1, n):
        S = i * m, m1 * (n - i), m2 * (n - i)
        ans = min(ans, max(S) - min(S))
    n1, n2 = n // 2, n - n // 2
    for i in range(1, m):
        S = i * n, n1 * (m - i), n2 * (m - i)
        ans = min(ans, max(S) - min(S))
    if n % 3 == 0 or m % 3 == 0: ans = 0
    elif n > 2: ans = min(ans, m)
    elif m > 2: ans = min(ans, n)
    assert(ans != 10 ** 10)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
x,y=map(int,input().split())
data=999999
if (x*y)%3==0:
    print(0)
    exit()
else:
    for i in range(1,max(x,y)):
        a=i*min(x,y)
        if (x*y-a)%2==0:
            data=int(min(data,max(a,(x*y-a)//2)-min(a,(x*y-a)//2)))
        else:
            b=((x*y-a)/2)-0.5*(max(x,y)-i)
            c=((x*y-a)/2)+0.5*(max(x,y)-i)
            data=int(min(data,max(a,b,c)-min(a,b,c)))
print(data)

Submission status: Wrong Answer

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

def w_div_3(H, W):
    w = W // 3
    rw = W - 2 * w
    return (rw - w) * H

def h_div_3(H, W):
    h = H // 3
    rh = H - 2 * h
    return (rh - h) * W

def w_div_h_div(H, W):
    min_diff = 10000000000
    for w in range(W):
        a1 = w * H
        a2 = (W - w) * (H // 2)
        a3 = W * H - a2 - a1
        diff = max(a1, a2, a3) - min(a1, a2, a3)
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(min(w_div_3(H, W), h_div_3(H, W), w_div_h_div(H, W), w_div_h_div(W, H)))

Submission status: Wrong Answer

Solution code:
def checkW(H, W, a):
    if W % 3 == 0:
        return 0
    x = int(W / 3) + a
    y = int(H / 2)
    S = [x*H, (W-x)*y, (W-x)*(H-y)]
    #print(x, y, S, max(S),min(S))
    return max(S) - min(S)

def checkH(H, W, a):
    if H % 3 == 0:
        return 0
    x = int(W / 2)
    y = int(H / 3) + a
    S = [W*y, x*(H-y), (W-x)*(H-y)]
    #print(x, y, S, max(S),min(S))
    return max(S) - min(S)

s = input().split(' ')
H = int(s[0])
W = int(s[1])
print(min(checkW(H,W,0), checkW(H,W,1),
          checkH(H,W,0), checkH(H,W,1)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
x,y=map(int,input().split())
data=[]
if (x*y)%3==0:
    print(0)
    exit()
else:
    for i in range(1,max(x,y)):
        a=i*min(x,y)
        if (x*y-a)%2==0:
            data.append(max(a,(x*y-a)//2)-min(a,(x*y-a)//2))
        else:
            b=((x*y-a)/2)-0.5*(max(x,y)-i)
            c=((x*y-a)/2)+0.5*(max(x,y)-i)
            data.append(max(a,b,c)-min(a,b,c))
print(int(min(data)))

Submission status: Wrong Answer

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


def calc3(h, w):
        W = H = "x"
        r = []
        for a in range(h/3-3, h/3+4):
                if a < 0 or a > h:
                        continue
                for b in range(w/2-2, w/2+3):
                        if b < 0 or b > w:
                                continue
                        S1 = a * w
                        S2 = (h - a) * b
                        S3 = (h - a) * (w - b)
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
                        r.append(q)
                for b in range((h-a)/2-2, (h-a)/2+3):
                        if b < 0 or b > h-a:
                                continue
                        S1 = a * w
                        S2 = b * w
                        S3 = (h - a - b) * w
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
        return min(r)

H, W = rdi()

print min(calc3(H, W), calc3(W, H))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
x,y=map(int,input().split())
data=[]
if (x*y)%3==0:
    print(0)
    exit()
else:
    for i in range(1,max(x,y)):
        a=i*min(x,y)
        if (x*y-a)%2==0:
            data.append(max(a,(x*y-a)//2)-min(a,(x*y-a)//2))
        else:
            b=((x*y-a)/2)-0.5*(max(x,y)-i)
            c=((x*y-a)/2)+0.5*(max(x,y)-i)
            data.append(max(a,b,c)-min(a,b,c))
print(min(data))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = 10 ** 10
m1, m2 = m // 2, m - m // 2
for i in range(1, n):
    S = i * m, m1 * (n - i), m2 * (n - i)
    ans = min(ans, max(S) - min(S))
n1, n2 = n // 2, n - n // 2
for i in range(1, m):
    S = i * n, n1 * (m - i), n2 * (m - i)
    ans = min(ans, max(S) - min(S))
if n % 3 == 0 or m % 3 == 0: ans = 0
elif n > 2: ans = min(ans, m)
elif m > 2: ans = min(ans, n)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = 10 ** 10
m1, m2 = m // 2, m - m // 2
for i in range(1, n):
    S = i * m, m1 * (n - i), m2 * (n - i)
    ans = min(ans, max(S) - min(S))
n1, n2 = n // 2, n - n // 2
for i in range(1, n):
    S = i * n, n1 * (m - i), n2 * (m - i)
    ans = min(ans, max(S) - min(S))
if n % 3 == 0 or m % 3 == 0: ans = 0
elif n > 2: ans = min(ans, m)
elif m > 2: ans = min(ans, n)
print(ans)

Submission status: Time Limit Exceeded

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,math.ceil(H/2)+1):
        for j in range(1,math.ceil(W/2)+1):
            a = [i*W,j*(H-i),(W-j)*(H-i)]
            b = max(a) - min(a)
            s.append(b)
            a = [H*j,(W-j)*i,(W-j)*(H-i)]
            b = max(a) - min(a)
            s.append(b)

    print(min(s))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
  print(0)
  exit()
ans = 1000000000
for change in range(2): #heightとwidthを入れ替えてもう一回実行する
  for ox in range(1,w):
    if not ox == w - 1:
      for tx in range(ox+1, w):
        ans = min(ans, h * (max(ox, tx-ox, w-tx) - min(ox, tx-ox, w-tx)))
    for ty in range(1, h):
      ans = min(ans, max(ty*w, ox*(h-ty), (w-ox)*(h-ty)) - min(ty*w, ox*(h-ty), (w-ox)*(h-ty)))
  temp = h
  h = w
  w = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:    # 3の倍数だったら最小値は0
    print(0)
    exit()
answer = float('inf')
h = 1
for _ in range(((H-1)//2)+1):
    a = h * W
    w = 1
    for _ in range(((W-1)//2)+1):
        b = (H-h) * w
        c = H * W - a - b
        MAX = max([a, b, c])
        MIN = min([a, b, c])
        if MAX - MIN <= answer:
            answer = MAX - MIN
        w += 1
    h += 1

w = 1
for _ in range(((W-1)//2)+1):
    a = w * H
    h = 1
    for _ in range(((H-1)//2)+1):
        b = (W-w) * h
        c = H * W - a - b
        MAX = max([a, b, c])
        MIN = min([a, b, c])
        if MAX - MIN <= answer:
            answer = MAX - MIN
        h += 1
    w += 1

print(answer)

Submission status: Time Limit Exceeded

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)//3,(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//3,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)//3,(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//3,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: Time Limit Exceeded

Solution code:
H, W = list(map(int,input().split()))
ans = H*W
h = H
w = W
for i in range(1,h//2+1):
    p1 = i*w
    for j in range(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(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(1,h//2+1):
    p1 = i*w
    for j in range(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(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: Time Limit Exceeded

Solution code:
def is_rect_in_HW(H, W, s1, s2, mem):
  s2_factors = factorize(s2, H, W, mem)
  
  res = []
  for  s2_factor in s2_factors:
    if s1[0] == s2_factor[0]: res.append([s1[0], s1_factor[1] + s1[1]])
    elif s1[0] != s1[1] and s1[1] == s2_factor[1]: res.append([s1[0] + s2_factor[0], s1[1]])
  return res

def factorize(num, H, W, mem):
  if num in mem:
    return mem[num]

  factors = set([])
  for i in range(1, min(num+1, max(H+1,W+1))):
    i2 = num//i
    if min(i,i2) > min(H,W) or max(i,i2) > max(H,W): continue
    if num % i == 0: factors.add(tuple(sorted([i,i2])))
  mem[num] = factors
  return factors


H, W = map(int, input().split())
S = int(H*W)
mem = {}
for del_s in range(S-2):
  for s1 in range(1,S-1):
    s3 = s1 + del_s
    s2 = S - s1 - s3
    if not (s1 <= s2 and s2<= s3): continue
    
    for s1_factor in factorize(s1, H, W, mem):
      res = is_rect_in_HW(H, W, s1_factor, s2, mem)
      if len(res) == 0: continue
      for tmp_s in res:
        res = is_rect_in_HW(H, W, sorted(tmp_s), s3, mem)
        #print(del_s, tmp_s, s1, s2, s3, res)
        if len(res) == 0: continue
        else:
          print(del_s)
          exit()

Submission status: Time Limit Exceeded

Solution code:

if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    if (W % 3 == 0) or (H % 3 == 0):
        print("0")
        exit()
    else:
        Ans = H*W
        for x in range(1, W):
            for y in range(1, H):
                # |--
                S1 = H*x
                S2 = (W - x) * y
                S3 = H*W - (S1 + S2)
                Ans1 = max(S1, S2, S3) - min(S1, S2, S3)

                # ---
                #  |
                S1 = y*W
                S2 = (H - y) * x
                S3 = H*W - (S1 + S2)
                Ans2 = max(S1, S2, S3) - min(S1, S2, S3)


                # | |
                S1 = x*H
                S2 = (W - x) // 2 * H
                S3 = H*W - (S1 + S2)
                Ans3 = max(S1, S2, S3) - min(S1, S2, S3)

                # --
                # --
                S1 = y*W
                S2 = (H - y) // 2 * W
                S3 = H*W - (S1 + S2)
                Ans4 = max(S1, S2, S3) - min(S1, S2, S3)

                # 最小値を更新
                Ans = min(Ans, Ans1, Ans2, Ans3, Ans4)

                # print("debug:(x, y) => (", x, y, ")")
                # print(Ans)
        print(Ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import math

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

result = 10**10

def vertical_and_horizontal_cal(h, w):
    global result
    area_1, area_2, area_3 = 0, 0, 0
    # - | このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area_1 = i * w
        area_2 = (h-i) * (w//2)
        area_3 = (h-i) * (w - w//2)
        diff = max(area_1, area_2, area_3) - min(area_1, area_2, area_3)
        if result > diff:
            result = diff

def vertical_and_vertical_cal(h, w):
    global result
    area_1, area_2, area_3 = 0, 0, 0
    # - - このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area_1 = i * w
        for j in range(1, math.ceil(h / 2) + 1 - i):
            area_2 = j * w
            area_3 = (h - i - j) * w
            diff = max(area_1, area_2, area_3) - min(area_1, area_2, area_3)
            if result > diff:
                result = diff

vertical_and_horizontal_cal(H, W)
vertical_and_horizontal_cal(W, H)
vertical_and_vertical_cal(H, W)
vertical_and_vertical_cal(W, H)

print(result)

Submission status: Time Limit Exceeded

Solution code:
choco=[int(i) for i in input().split()]
size_list01=[[a1*choco[0], (choco[1]-a1)*a0, (choco[1]-a1)*(choco[0]-a0)] for a1 in range(choco[1]) for a0 in range(choco[0])]
size_list1=[[a10,a11,choco[1]-a10-a11] for a11 in range(choco[1]) for a10 in range(choco[1]-a11)]
size_list0=[[a00,a01,choco[0]-a00-a01] for a01 in range(choco[0]) for a00 in range(choco[0]-a01)]
diff01=[max(i)-min(i) for i in size_list01]
diff0=[max(i)-min(i) for i in size_list0]
diff1=[max(i)-min(i) for i in size_list1]

print(min(min(diff01),min(diff0)*choco[1],min(diff1)*choco[0]))

Submission status: Time Limit Exceeded

Solution code:
choco=[int(i) for i in input().split()]
size_list01=[[a1*choco[0], (choco[1]-a1)*a0, (choco[1]-a1)*(choco[0]-a0)] for a1 in range(choco[1]) for a0 in range(choco[0])]
size_list1=[[a10*choco[0],a11*choco[0],(choco[1]-a10-a11)*choco[0]] for a11 in range(choco[1]) for a10 in range(choco[1]-a11)]
size_list0=[[a00*choco[1],a01*choco[1],(choco[0]-a00-a01)*choco[1]] for a01 in range(choco[0]) for a00 in range(choco[0]-a01)]
size_list=size_list01+size_list0+size_list1
diff=[max(i)-min(i) for i in size_list]
print(min(diff))

Submission status: Time Limit Exceeded

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(1, h):
        for j in range(1, w):
            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: Time Limit Exceeded

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で縦分割
        for _h in range(1, math.ceil(H / 2) + 1):
            S = [
                H * _w,
                (W - _w) * _h,
                (W - _w) * (H - _h),
            ]
            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: Time Limit Exceeded

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):
    # 縦MAX, H>=2より、W-1まで確認
    if answer is None:
        answer = float("inf")

    for _w in range(1, W):
        # 縦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で縦分割
        for _h in range(1, H):
            S = [
                H * _w,
                (W - _w) * _h,
                (W - _w) * (H - _h),
            ]
            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: Time Limit Exceeded

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

if H%3==0 or W%3==0:
    print(0)
elif min(H, W)%2==0:
    print(min(H, W)//2)
else:
    S = []
    for i in range(2, W//2+1):
        for j in range(2, H//2+1):
            a = H * i
            b = (W - i) * j
            c = (H - j) * (W - i)
            S.append(max([a, b, c]) - min([a, b, c]))
    for i in range(2, W//2+1):
        for j in range(2, H//2+1):
            a = W * i
            b = (H - i) * j
            c = (W - j) * (H - i)
            S.append(max([a, b, c]) - min([a, b, c]))
    print(min(S))

Submission status: Time Limit Exceeded

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


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

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


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


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

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

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

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

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

    return S

print(get_slice())