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:
H,W = map(int,input().split())
a = H%2
b = W%2
ans = 10**9
if H%3==0 or W%3==0:
    print(0)
elif H==1 or W==1:
    print(1)
else:
    for i in range(1,W):
        c = (H*i,H//2*(W-i),H*W-H*i-(H//2)*(W-i))
        ans = min(ans,max(c)-min(c))
        c = (H*i,(W-i)//2*H,H*W-H*i-(W-i)//2*H)
        ans = min(ans,max(c)-min(c))
    for i in range(1,H):
        c = (W*i,W//2*(H-i),H*W-W*i-(W//2)*(H-i))
        ans = min(ans,max(c)-min(c))
        c = (W*i,(H-i)//2*W,H*W-W*i-(H-i)//2*W)
        ans = min(ans,max(c)-min(c))
    
    print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
ans=[]
import sys
def s(a,b):
    for i in range(a):
        s=a*b
        x=i*b
        y=((a-i)//2)*b
        z=s-x-y

        d=(a-i)*(b//2)
        e=s-x-d
        ma=max(x,y,z)
        mi=min(x,y,z)
        mc=max(x,e,d)
        mn=min(x,e,d)
        res=min((ma-mi),(mc-mn))
        ans.append(res)
    return min(ans)
        
f=s(h,w)
g=s(w,h)
print(min(f,g))
    
# print(ans)
# print(min(ans))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [h*w] * 4

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

if w > 2:
  s[0] = h
if h > 2:
  s[1] = w
if h % 2 == 0:
  s[2] = h // 2
else:
  tmp = h*w
  for i in range(w//3, w//3+2):
    s1 = i * h
    s2 = (w-i) * (h//2)
    s3 = (w-i) * (h//2 + 1)
    tmp = min(tmp, max(s1, s2, s3) - min(s1, s2, s3))
  s[2] = tmp
if w % 2 == 0:
  s[3] = w // 2
else:
  tmp = h*w
  for i in range(h//3, h//3 + 2):
    s1 = i * w
    s2 = (h-i) * (w//2)
    s3 = (h-i) * (w//2 + 1)
    tmp = min(tmp, max(s1, s2, s3) - min(s1, s2, s3))
  s[3] = tmp

print(min(s))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h==2 and w==2:
  print(1)
  exit()
ans=10**10
if h>=3:
  if h%3==0:
    a=0
  else:
    a=w
  if a<ans:
    ans=a
if w>=3:
  if w%3==0:
    a=0
  else:
    a=h
  if a<ans:
    ans=a
if h>1:
  b=h//3
  x1=w*b
  x2=(h-b)*(w//2)
  x3=h*w-x1-x2
  a=max(x1,x2,x3)-min(x1,x2,x3)
  if a<ans:
    ans=a
  x1=w*(b+1)
  x2=(h-b-1)*(w//2)
  x3=h*w-x1-x2
  a=max(x1,x2,x3)-min(x1,x2,x3)
  if a<ans:
    ans=a
  b=w//3
  x1=h*b
  x2=(w-b)*(h//2)
  x3=h*w-x1-x2
  a=max(x1,x2,x3)-min(x1,x2,x3)
  if a<ans:
    ans=a
  x1=h*(b+1)
  x2=(w-b-1)*(h//2)
  x3=h*w-x1-x2
  a=max(x1,x2,x3)-min(x1,x2,x3)
  if a<ans:
    ans=a
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor
H,W=map(int,input().split())
a=float("inf")
b=0
c=-float("inf")
mi=float("inf")
if W>2:                             #縦のみ
    if W%3==0:
        a=(H*W)//3
        b=(H*W)//3
        c=(H*W)//3
    elif W%3==1:
        a=H*(W//3)
        b=H*(W//3)
        c=H*((W//3)+1)
    else:
        a=H*(W//3)
        b=H*((W//3)+1)
        c=H*((W//3)+1)
    mi=min(mi,max(a,b,c)-min(a,b,c))
if H>2:                             #横のみ
    if H%3==0:
        a=(H*W)//3
        b=(H*W)//3
        c=(H*W)//3
    elif H%3==1:
        a=W*(H//3)
        b=W*(H//3)
        c=W*((H//3)+1)
    else:
        a=W*(H//3)
        b=W*((H//3)+1)
        c=W*((H//3)+1)
    mi=min(mi,max(a,b,c)-min(a,b,c))

for i in range(1,H,1):#1ぽんの横線引く場所
    a = float("inf")
    b = W*i
    c = -float("inf")
    H1=ceil((H-i)/2)
    H2=floor((H-i)/2)
    W1=ceil(W/2)
    W2=floor(W/2)
    mi=min(mi,max(W*H1,b,W*H2)-min(W*H1,b,W*H2),max((H-i)*W1,b,(H-i)*W2)-min((H-i)*W1,b,(H-i)*W2))

for i in range(1,W,1):#1ぽんの縦線引く場所
    a = float("inf")
    b = H*i
    c = -float("inf")
    W1=ceil((W-i)/2)
    W2=floor((W-i)/2)
    H1=ceil(H/2)
    H2=floor(H/2)
    mi=min(mi,max((W-i)*H1,b,(W-i)*H2)-min((W-i)*H1,b,(W-i)*H2),max(W1*H,b,W2*H)-min(W1*H,b,W2*H))
print(mi)

Submission status: Accepted

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

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

for i in range(1, H):
    S1 = i*W
    
    if W%2==0:
        S2 = (H-i)*(W//2)
        S3 = S2
    else:
        S2 = (H-i)*(W//2+1)
        S3 = H*W-S1-S2
    
    ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

H, W = W, H

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

for i in range(1, H):
    S1 = i*W
    
    if W%2==0:
        S2 = (H-i)*(W//2)
        S3 = S2
    else:
        S2 = (H-i)*(W//2+1)
        S3 = H*W-S1-S2
    
    ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

print(ans)

Submission status: Accepted

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

def defs(h, w):
    ans = 10 ** 12
    for i in range(1, h):
        sa = i * w
        h2 = h - i

        for j in range(2):
            if j == 0:
                sb = h2 * (w // 2)
                sc = h2 * (w - (w // 2))
            else:
                sb = (h2 // 2) * w
                sc = (h - i - (h2 // 2)) * w

            s_max = max(sa, sb, sc)
            s_min = min(sa, sb, sc)

            ans = min(ans, s_max - s_min)
    return ans

print(min(defs(h, w), defs(w, h)))

Submission status: Accepted

Solution code:
def f(x,y,z):
    return max(x,y,z)-min(x,y,z)

h, w = map(int, input().split())
l = []
ans1, ans2 = h*w, h*w
for i in range(1,h//2+1):
        s1 = i*w
        s2 = w*((h-i)//2)
        s3 = h*w-s1-s2
        s4 = (h-i)*(w//2)
        s5 = h*w-s1-s4
        ans1 = min(ans1, f(s1,s2,s3),f(s1,s4,s5))

for i in range(1,w//2+1):
        s1 = i*h
        s2 = h*((w-i)//2)
        s3 = h*w-s1-s2
        s4 = (w-i)*(h//2)
        s5 = h*w-s1-s4
        ans2 = min(ans2, f(s1,s2,s3),f(s1,s4,s5))
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
import sys

def solve(h, w):
  res = [((h + 2) // 3 - h // 3) * w]
  for d in [h // 3, (h + 2) // 3]:
    cand = sorted([d * w, (h - d) * (w // 2), (h - d) * ((w + 1) // 2)])
    res.append(cand[-1] - cand[0])
  return min(res)

h, w = map(int, sys.stdin.readline().split())

def main():
  print(min(solve(h, w), solve(w, h)))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  H,W = readInts()
  LIST = [H//2 + W//3 + 1, W//3 + H//2 + 1, H, W]
  if H%3 == 0 or W % 3 == 0:
    LIST += [0]
  if H % 2 == 0:
    LIST += [H//2]
  if W % 2 == 0:
    LIST += [W//2]
  print(min(LIST))
  
if __name__ == '__main__':
  main()

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
  for i in range(1,max(h,w)//2 + 1):
    a = min(h,w)*i
    b = (max(h,w)-i)*(min(h,w)//2)
    if min(h,w)%2 != 0:
      c = (max(h,w)-i)*(min(h,w)//2 + 1)
    else:
      c = b
    kari = max(a,b,c)-min(a,b,c)
    if ans > kari:
      ans = kari
  ans3 = h*w
  for i in range(1,min(h,w)//2 + 1):
    a = max(h,w)*i
    b = (min(h,w)-i)*(max(h,w)//2)
    if max(h,w)%2 != 0:
      c = (min(h,w)-i)*(max(h,w)//2 + 1)
    else:
      c = b
    kari = max(a,b,c)-min(a,b,c)
    if ans3 > kari:
      ans3 = kari
  ans2 = ((max(h,w)//3 + 1)*min(h,w))-((max(h,w)//3)*min(h,w))
  print(min(ans,ans2,ans3))

Submission status: Accepted

Solution code:
#!/usr/bin/env pytHon3
# -*- coding: utf-8 -*-


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

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

    area = H * W / 3
    result = min(H, W)

    for H1 in range(1, H):
        if area // H1 > W:
            continue
        else:
            W1s = [int(area // H1), int(area // H1) + 1]

        for W1 in W1s:
            if W1 == W:
                continue
            else:
                H2 = H - H1
                W2s = [W1, W]

            for W2 in W2s:
                W3 = W - W1
                if W2 == W1:
                    H3 = H
                else:
                    H3 = H1

                areas = [H1 * W1, H2 * W2, H3 * W3]
                if max(areas) - min(areas) < result:
                    result = max(areas) - min(areas)

    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input().split(" ")
H = int(S[0])
W = int(S[1])


def calculate(h, w):
    result = []
    for i in range(1, h):
        s1 = w * i
        s2 = (h - i) * (w // 2)
        s3 = (h - i) * w - s2

        minValue = min(min(s1, s2), s3)
        maxValue = max(max(s1, s2), s3)

        result.append(maxValue - minValue)

        if i <= h - 1:
            s1 = w * i
            s2 = ((h - i) // 2) * w
            s3 = (h - i) * w - s2
            minValue = min(min(s1,s2),s3)
            maxValue = max(max(s1,s2),s3)
            result.append(maxValue - minValue)

    for i in range(1, w):
        if i <= w - 1:
            s1 = i * h
            s2 = ((w - i) // 2) * h
            s3 = (w - i) * h - s2

            minValue = min(min(s1, s2), s3)
            maxValue = max(max(s1, s2), s3)
            result.append(maxValue - minValue)

        s1 = i * h
        s2 = (w - i) * (h //2)
        s3 = (w - i) * h - s2
        minValue = min(min(s1, s2), s3)
        maxValue = max(max(s1, s2), s3)
        result.append(maxValue - minValue)

    print(min(result))

calculate(H, W)

Submission status: Accepted

Solution code:
def solve(s1, s2, s3):
    S = [s1, s2, s3]
    return(max(S) - min(S))


H, W = map(int, input().split())
S = H * W
for j in range(1, W):
    S1 = H * j
    i = H // 2
    S2 = (W - j) * i
    S3 = (W - j) * (H - i)
    S = min(S, solve(S1, S2, S3))

for i in range(1, H):
    S1 = W * i
    j = W // 2
    S2 = (H - i) * j
    S3 = (H - i) * (W - j)
    S = min(S, solve(S1, S2, S3))

S = min(S, H * (W % 3 > 0))
S = min(S, W * (H % 3 > 0))


print(S)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

ans=float('inf')
for i in range(1,w):
    tmp1=h*i
    tmp2=h*((w-i)//2)
    tmp3=h*(w-i-(w-i)//2)
    if tmp2!=0:
        ans=min(ans,max(tmp1,tmp2,tmp3)-min(tmp1,tmp2,tmp3))
    tmp2=(w-i)*(h//2)
    tmp3=(w-i)*(h-h//2)
    ans=min(ans,max(tmp1,tmp2,tmp3)-min(tmp1,tmp2,tmp3))

h,w=w,h
for i in range(1,w):
    tmp1=h*i
    tmp2=h*((w-i)//2)
    tmp3=h*(w-i-(w-i)//2)
    if tmp2!=0:
        ans=min(ans,max(tmp1,tmp2,tmp3)-min(tmp1,tmp2,tmp3))
    tmp2=(w-i)*(h//2)
    tmp3=(w-i)*(h-h//2)
    ans=min(ans,max(tmp1,tmp2,tmp3)-min(tmp1,tmp2,tmp3))
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=H*W
if(W%3==0):
  ans=0
else:
  ans=min(ans,H)
x=W//3
s1=x*H
s2=(W-x)*(H//2)
s3=(W-x)*H-s2
ans=min(ans,max(s1,max(s2,s3))-min(s1,min(s2,s3)))

x=W//3+1
s1=x*H
s2=(W-x)*(H//2)
s3=(W-x)*H-s2
#print(s1,s2,s3)
ans=min(ans,max(s1,max(s2,s3))-min(s1,min(s2,s3)))

a=H
H=W
W=a
if(W%3==0):
  ans=0
else:
  ans=min(ans,H)
x=W//3
s1=x*H
s2=(W-x)*(H//2)
s3=(W-x)*H-s2
ans=min(ans,max(s1,max(s2,s3))-min(s1,min(s2,s3)))

x=W//3+1
s1=x*H
s2=(W-x)*(H//2)
s3=(W-x)*H-s2
ans=min(ans,max(s1,max(s2,s3))-min(s1,min(s2,s3)))

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
def choco(H, W):
    ans = float("inf")
    a, b, c = 0, 0, 0
    for i in range(1, H):
        a = i*W
        for j in range(2):
            if j == 0:
                b = (H-i)//2 * W
                c = H*W - a - b 
            else:
                b = (H-i)*(W//2)
                c = H*W - a - b
            ans = min(ans, max(a, b, c) - min(a, b, c))
    return ans

print(min(choco(h, w), choco(w, h)))

Submission status: Accepted

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

if h%3==0:
    d=0
elif w%3==0:
    d=0
else:
    if h>=w:
        h,w=w,h
    d1=h
    d2min=h*w
    for ww in range(1,w):
        h1=h//2
        h2=h-h1
        d2=max(ww*h,(w-ww)*h2)-min(ww*h,(w-ww)*h1)
#        print(d2,max(ww*h,(w-ww)*h2),min(ww*h,(w-ww)*h1))
        d2min=min(d2,d2min)

    for hh in range(1,h):
        w1=w//2
        w2=w-w1
        d2=max(hh*w,(h-hh)*w2)-min(hh*w,(h-hh)*w1)
#        print(d2,max(ww*h,(w-ww)*h2),min(ww*h,(w-ww)*h1))
        d2min=min(d2,d2min)

    d=min(d1,d2min)
print(d)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s_h_list = []
for i in range(1, h):
	sa = w * i
	sb = (w//2) * (h-i)
	sc = h*w - (sa + sb)
	s_list = [sa, sb, sc]
	s_h_list.append(max(s_list) - min(s_list))
	sb = ((h-i)//2) * w
	sc = h*w - (sa + sb)
	s_list = [sa, sb, sc]
	s_h_list.append(max(s_list) - min(s_list))
s_h_list.sort()
s_w_list = []
for i in range(1, w):
	sa = h * i
	sb = (h//2) * (w-i)
	sc = h*w - (sa + sb)
	s_list = [sa, sb, sc]
	s_w_list.append(max(s_list) - min(s_list))
	sb = h * ((w-i)//2)
	sc = h*w - (sa + sb)
	s_list = [sa, sb, sc]
	s_w_list.append(max(s_list) - min(s_list))
s_w_list.sort()
print(min([s_h_list[0], s_w_list[0]]))

Submission status: Accepted

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

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

for a, b in ((H, W), (W, H)):
    tmp = (a // 3 * b, (a - a // 3) * (b // 2), (a - a // 3) * (b - b // 2))
    ans = min(ans, max(tmp) - min(tmp))
    tmp = ((a // 3 + 1) * b, (a - a // 3 - 1) * (b // 2), (a - a // 3 - 1) * (b - b // 2))
    ans = min(ans, max(tmp) - min(tmp))

print(ans)

Submission status: Accepted

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

candicate=[]
for y in range(1, H):
    #print(y)
    candicate.append(max(y*W, W * (((H-y)+1)//2)) - min(y*W, W* ((H-y)//2)))
    candicate.append(max(y*W, (H-y)*((W+1)//2)) - min(y*W, (H-y)* (W//2)))

for x in range(1, W):
    candicate.append(max(x*H, H * (((W-x)+1)//2)) - min(x*H, H* ((W-x)//2)))
    candicate.append(max(x*H, (W-x) * ((H+1)//2)) - min(x*H, (W-x)* (H//2)))
#print(candicate)
print(min(candicate))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
def solve(h,w):
    ans=h*w
    for i in range(1,h):
        #h-i height left 
        a=(h-i)*(w//2)
        b=(h-i)*w-a
        ans=min(ans,max(i*w,a,b)-min(i*w,a,b))
        a=((h-i)//2)*(w)
        b=(h-i)*w-a
        ans=min(ans,max(i*w,a,b)-min(i*w,a,b))
    return ans
print(min(solve(h,w),solve(w,h)))

Submission status: Accepted

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

ans = h*w

for a,b in [(h,S//(3*h)),(h,S//(3*h)+1),(S//(3*w),w),(S//(3*w)+1,w)]:
    
    s_list = [a*b]
    hr = h - a*(a<h)
    wr = w - b*(b<w)
    
    if (hr*wr)%2 == 0:
        s_list += [hr*wr//2]
    else:
        s_list += [min(hr,wr)*(max(hr,wr)//2), min(hr,wr)*(max(hr,wr)//2+1)]
    ans = min(ans, max(s_list)-min(s_list))
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
#from scipy.misc import comb

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

if H%3 == 0:
    print(0)
elif W%3 == 0:
    print(0)
else:
    ans = H*W
    A = [0]*3
    for i in range(1,H):
        A[0] = i*W
        A[1] = (H-i)*(W//2)
        A[2] = (H-i)*(W-W//2)
        A.sort()
        ans = min(ans,A[2]-A[0])
    
    for j in range(1,W):
        A[0] = H*j
        A[1] = (H//2)*(W-j)
        A[2] = (H-H//2)*(W-j)
        A.sort()
        ans = min(ans,A[2]-A[0])

    ans = min(ans, H, W)

    print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=s=h*w
def f(x,y):
  global m
  g=lambda:min(m,max(p,q,r)-min(p,q,r))
  for i in (x//3,x//3+1):
    p=i*y
    q=(x-i)//2*y; r=s-p-q; m=g()
    q=y//2*(x-i); r=s-p-q; m=g()
  return m
f(h,w);f(w,h)
print(m)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    ans = 10 ** 9
    for _ in range(2):
        for i in range(1, w):
            c1 = h * i
            c2 = (h // 2) * (w - i)
            c3 = h * w - c1 - c2
            maxc = max(c1, c2, c3)
            minc = min(c1, c2, c3)
            if maxc - minc < ans:
                ans = maxc - minc
        h, w = w, h
    if ans > min(h, w):
        ans = min(h, w)
print(ans)

Submission status: Accepted

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

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

ans = min(h, w)

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

h, w = w, h

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

Submission status: Accepted

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

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

res = h * w
for l in permutations((h, w), 2):
    for i in range(1, l[0]):
        s1 = i * l[1]
        for m in permutations((l[0] - i, l[1]), 2):
            s2 = floor(m[0] / 2) * m[1]
            s3 = ceil(m[0] / 2) * m[1]
            val = max(s1, s2, s3) - min(s1, s2, s3)
            if val < res:
                res = val

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
H,W=map(int,input().split())
d=[H,W],[W,H]
ans=10**15
for x,y in d:
    for i in range(1,x):
        A=(x-i)*y;B=i*y
        if(i%2==0 or y%2==0):
            ans=min(ans,max(A,B//2)-min(A,B//2))
        else:
            e=[y,i],[i,y]
            for c,d in e:
                C=math.floor(c/2)*d;D=math.ceil(c/2)*d
                ans=min(ans,max(A,C,D)-min(A,C,D))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)

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

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

    ans = min(h,w)

    h2 = h//2
    for i in range(1,w):
        S = [h2 * i, (h - h2) * i, h * (w - i)]
        S.sort()
        ans = min(ans,S[-1] - S[0])
    
    w2 = w//2
    for i in range(1,h):
        S = [w2 * i, (w - w2) * i, w * (h - i)]
        S.sort()
        ans = min(ans,S[-1] - S[0])
    
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def main():
  h, w = map(int, input().split())
  S = h*w
  if S%3==0:
    return 0

  ds = [h, w]
  
  h1 = (h+1)//3
  s1 = h1*w; s2 = w//2*(h-h1); s3 = S-s1-s2
  ds.append(max(s1,s2,s3)-min(s1,s2,s3))
  
  w1 = (w+1)//3
  s1 = w1*h; s2 = h//2*(w-w1); s3 = S-s1-s2
  ds.append(max(s1,s2,s3)-min(s1,s2,s3))
  
  return min(ds)

print(main())

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = H*W
ans = 10**10
for i in range(1,H):
  if (H-i)*W%2==0:
    m = (H-i)*W//2
    ans = min(ans, abs(i*W-m))
  else:
    if (H-i)<W:
      m1,m2 = (H-i)*(W//2), (H-i)*(W//2+1)
      x = max(abs(m1-m2), abs(m2-i*W), abs(m1-i*W))
      ans = min(ans,x)
    else:
      m1,m2 = W*((H-i)//2), W*((H-i)//2+1)
      x = max(abs(m1-m2), abs(m2-i*H), abs(m1-i*H))
      ans = min(ans,x)

for i in range(1,W):
  if H*(W-i)%2==0:
    m = H*(W-i)//2
    ans = min(ans, abs(i*H-m))
  else:
    if H>W-i:
      m1,m2 = (W-i)*(H//2), (W-i)*(H//2+1)
      x = max(abs(m1-m2), abs(m2-i*H), abs(m1-i*H))
      ans = min(ans,x)
    else:
      m1,m2 = H*((W-i)//2), H*((W-i)//2+1)
      x = max(abs(m1-m2), abs(m2-i*H), abs(m1-i*H))
      ans = min(ans,x)

print(ans)

Submission status: Accepted

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

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

    if w == 2:
        a = 1
        a1 = a * h
        b = h // 2
        a2 = (w-a) * b
        a3 = (w-a) * (h-b)
        ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))
    else:
        for i in range(3):
            a = w // 3 + i
            a1 = a * h
            b = h // 2
            a2 = (w-a) * b
            a3 = (w-a) * (h-b)
            ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))

    if h == 2:
        a = 1
        a1 = a * w
        b = w // 2
        a2 = (h-a) * b
        a3 = (h-a) * (w-b)
        ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))
    else:
        for i in range(3):
            a = h // 3 + i
            a1 = a * w
            b = w // 2
            a2 = (h-a) * b
            a3 = (h-a) * (w-b)
            ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))
    
    print(ans)

Submission status: Accepted

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

#縦に3分割する場合
d1 = (H + 2) // 3 * W - H // 3 * W
#横に3分割する場合
d2 = (W + 2) // 3 * H - W // 3 * H
#縦に2分割，残りを横に2分割する場合
d3 = 10**18
for i in range(W + 1):
    d = max(H * i, (H + 1) // 2 * (W - i), H // 2 * (W - i)) - min(H * i, (H + 1) // 2 * (W - i), H // 2 * (W - i))
    d3 = min(d3, d)
#横に2分割，残りを縦に2分割する場合
d4 = 10**18
for i in range(H + 1):
    d = max(W * i, (W + 1) // 2 * (H - i), W // 2 * (H - i)) - min(W * i, (W + 1) // 2 * (H - i), W // 2 * (H - i))
    d3 = min(d3, d)
    
print(min(d1, d2, d3, d4))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()

ans = INF

for i in range(2):
    if i == 1:
        H, W = W, H
    for a in range(1, H):
        bc = H - a
        b = int(bc/2)
        c = bc - b
        sa, sb, sc = a * W, b * W, c * W
        s = max(sa, sb, sc) - min(sa, sb, sc)
        ans = min(s, ans)
    for a in range(1, H):
        bc = H - a
        b = int(W/2)
        c = W - b
        sa, sb, sc = a * W, b * bc, c * bc
        s = max(sa, sb, sc) - min(sa, sb, sc)
        ans = min(s, ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

H,W = list(map(int, input().rstrip().split()))
#-----

def check(h,w):
    area_diff = h*w

    for i in range(1,h//2+1):
        # 横3分割
        area = [ i*w , ((h-i)//2)*w , ((h-i)//2 + (h-i)%2)*w ]
        area.sort()
        diff = area[2] - area[0]
        area_diff = min( area_diff , diff )
        
        # 横1分割、縦2分割
        area = [ i*w , (h-i)*(w//2) , (h-i)*(w//2 + w%2) ]
        area.sort()
        diff = area[2] - area[0]
        area_diff = min( area_diff , diff )

    return area_diff
#-----


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

res1 = check(H,W)
res2 = check(W,H)
print( min(res1,res2) )

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


H, W = MI()

pieces = H * W


memo = dict()
def divide(h, w):
    if memo.get((h, w)) is not None:
        return memo[(h, w)]
    elif memo.get((w, h)) is not None:
        return memo[(w, h)]
    p = h * w
    if w > 1:
        a1 = w // 2 * h
        a2 = p - a1
        memo[(h, w)] = (a1, a2)
    if h > 1:
        b1 = h // 2 * w
        b2 = p - b1
        if memo.get((h, w)) is not None:
            a1, a2 = memo[(h, w)]
            if abs(a1 - a2) > abs(b1 - b2):
                memo[(h, w)] = (b1, b2)
    return memo[(h, w)]


ans = float('inf')
for i in range(1, W):
    p1 = i * H
    p2, p3 = divide(W - i, H)
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))
for i in range(1, H):
    p1 = i * W
    p2, p3 = divide(H - i, W)
    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))
print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
ans=a
for i in range(a):
   x=i*b
   a2=a-i
   if a2*b%2==0:
     y=a2*b//2
   else:
     y=min(a2*(b+1)//2,(a2+1)*b//2)
   z=a2*b-y
   diff=max(x,y,z)-min(x,y,z)
   ans=min(ans,diff)
for i in range(b):
   x=i*a
   b2=b-i
   if b2*a%2==0:
     y=b2*a//2
   else:
     y=min(b2*(a+1)//2,(b2+1)*a//2)
   z=b2*a-y
   diff=max(x,y,z)-min(x,y,z)
   ans=min(ans,diff)
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')

    # 横と縦の切るところを真ん中に固定してそれぞれのパターンを線形検索
    center = W//2
    for i in range(1, H):
        # 縦を先に割る
        a1 = center * H
        a2 = (W-center) * i
        a3 = (W-center) * (H-i)

        # 横を先に割る
        b1 = i * W
        b2 = (H-i) * center
        b3 = (H-i) * (W-center)
        ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))
        ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))

    center = H//2
    for i in range(1, W):
        # 縦を先に割る
        a1 = i * H
        a2 = (W-i) * center
        a3 = (W-i) * (H-center)

        # 横を先に割る
        b1 = center * W
        b2 = (H-center) * i
        b3 = (H-center) * (W-i)
        ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))
        ans = min(ans, max(b1, b2, b3) - min(b1, b2, b3))

    # 3つに分割
    ans = min(ans, (H//3+1)*W - (H//3)*W)
    ans = min(ans, (W//3+1)*H - (W//3)*H)

    print(ans)

Submission status: Accepted

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

H, W = [int(x) for x in input().split()]
S = H * W
res1 = 10 ** 10
res2 = 10 ** 10

# ヨコ向きに一枚切る
for i in range(1, H):
    S1 = i * W
    x = W
    y = H - i

    # ヨコに半分
    S2 = (y // 2) * x
    S3 = S - S1 - S2
    res1 = min(res1, max(S1, S2, S3) - min(S1, S2, S3))

    # タテに半分
    S2 = y * (x // 2)
    S3 = S - S1 - S2
    res1 = min(res1, max(S1, S2, S3) - min(S1, S2, S3))

# タテ向きに一枚切る
for j in range(1, W):
    S1 = H * j
    x = W - j
    y = H

    # ヨコに半分
    S2 = (y // 2) * x
    S3 = S - S1 - S2
    res2 = min(res2, max(S1, S2, S3) - min(S1, S2, S3))

    # タテに半分
    S2 = y * (x // 2)
    S3 = S - S1 - S2
    res2 = min(res2, max(S1, S2, S3) - min(S1, S2, S3))

print(min(res1, res2))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W=MI()
    if (H*W)%3==0:
        print(0)
    else:
        def tw(h,w):
            #2つに分ける
            if (h*w)%2==0:
                return h*w//2,h*w//2
            else:
                a=h//2*w
                b=h*w - a
                c=w//2*h
                d=h*w - c
                if abs(a-b)<=abs(c-d):
                    return a,b
                else:
                    return c,d
                
            
        ans=10**10
        s=[0,0,0]
        #一個目を，長さW高さiにする，iを探索
        for i in range(1,H):
            s[0]=i*W
            s[1],s[2]=tw(H-i,W)
            temp=max(s)-min(s)
            ans=min(ans,temp)
            
        for j in range(1,W):
            s[0]=j*H
            s[1],s[2]=tw(H,W-j)
            temp=max(s)-min(s)
            ans=min(ans,temp)
        print(ans)
            
    
            

main()

Submission status: Accepted

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