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

Solution (Python):
def main():
    h,w = map(int,input().split())
    
    h1 = h//3
    h2 = (h-h1)//2
    h3 = h-h1-h2
    ans = (max(h1,h2,h3)-min(h1,h2,h3))*w
    
    w1 = w//3
    w2 = (w-w1)//2
    w3 = w-w1-w2
    a = (max(w1,w2,w3)-min(w1,w2,w3))*h
    if a<ans:
        ans = a
    
    h1 = h//3
    h2 = h-h1
    w1 = w//2
    w2 = w-w1
    a = max(h1*w,h2*w1,h2*w2)-min(h1*w,h2*w1,h2*w2)
    if a<ans:
        ans = a
    h1 = h//3+1
    h2 = h-h1
    w1 = w//2
    w2 = w-w1
    a = max(h1*w,h2*w1,h2*w2)-min(h1*w,h2*w1,h2*w2)
    if a<ans:
        ans = a
    
    w1 = w//3
    w2 = w-w1
    h1 = h//2
    h2 = h-h1
    a = max(w1*h,w2*h1,w2*h2)-min(w1*h,w2*h1,w2*h2)
    if a<ans:
        ans = a
    w1 = w//3+1
    w2 = w-w1
    h1 = h//2
    h2 = h-h1
    a = max(w1*h,w2*h1,w2*h2)-min(w1*h,w2*h1,w2*h2)
    if a<ans:
        ans = a
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
ans = float("inf")
for i in range(1,h+1):
    if w % 2 == 1 and (h-i) % 2 == 1:
        ans = min(ans, max(w*i, (h-i)*(w//2), (h-i)*(w//2+1))-min(w*i, (h-i)*(w//2), (h-i)*(w//2+1)))
    elif (h-i) % 2 == 0:
        ans = min(ans, max(w*i, (h-i)//2*w)-min(w*i, (h-i)//2*w))
    else:
        ans = min(ans, max(w*i, (h-i)*(w//2))-min(w*i, (h-i)*(w//2)))
h, w = w, h
for i in range(1,h+1):
    if w % 2 == 1 and (h-i) % 2 == 1:
        ans = min(ans, max(w*i, (h-i)*(w//2), (h-i)*(w//2+1))-min(w*i, (h-i)*(w//2), (h-i)*(w//2+1)))
    elif (h-i) % 2 == 0:
        ans = min(ans, max(w*i, (h-i)//2*w)-min(w*i, (h-i)//2*w))
    else:
        ans = min(ans, max(w*i, (h-i)*(w//2))-min(w*i, (h-i)*(w//2)))
print(ans)

Solution (Python):
h,w = map(int,input().split())
def func(a,b):
  ret = []
  for h1 in (a//3,a//3+1):
    a1 = h1*b
    nh = a-h1
    c = (a1,nh//2*b,(nh-nh//2)*b)
    ret.append(max(c)-min(c))
    c = (a1,nh*(b//2),nh*(b-b//2))
    ret.append(max(c)-min(c))
  return min(ret)
print(min(func(h,w),func(w,h)))

Solution (Python):
def calc(h, w):
  ans = (h+1)*(w+1)
  cut_1 = h//2
  cut_2 = h//2 + (h%2 == 1)
  for i in range(1, w):
    s1 = [h*i, cut_1*(w-i), cut_2*(w-i)]
    s2 = [h*i, h*((w-i)//2), h*((w-i)//2+ ((w-i)%2 == 1))]
    ans = min([ans, max(s1)-min(s1), max(s2)-min(s2)])
  return ans
def main():
  a, b = map(int,  input().split())
  print(min([calc(a,  b), calc(b, a)]))
  
if __name__ == "__main__":
  main()

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    H, W = mapline()
    ans = INF
    for i in range(2):
        H, W = W, H
        for h in range(1, H):
            _ans = 0
            A = h * W
            
            B1 = math.ceil(W/2) * (H-h)
            C1 = math.floor(W/2) * (H-h)
            _ans = max([abs(A - B1), abs(B1 - C1), abs(A - C1)])
            ans = min(_ans, ans)
            
            _ans = 0
            if H*W <= 3 * A:
                w = math.ceil(A // (H-h))
                B2 = (H-h) * w
                C2 = (H-h) * (W-w)
                _ans = max([abs(A - B2), abs(B2 - C2), abs(A - C2)])
                ans = min(_ans, ans)
            
            _ans = 0
            h2 = math.ceil((H-h) / 2)
            if h + h2 != H:
                C3 = W * (H - h2 - h)
                B3 = W * h2
                _ans = max([abs(A - B3), abs(B3 - C3), abs(A - C3)])
                ans = min(_ans, ans)

    print(ans)


if __name__ == "__main__":
    
    run()

Solution (Python):
H,W = map(int,input().split())
def HW(H,W):
    if H%2 == 0 or W%2 == 0:
        return [H*W//2]*2
    else:
        A = min((H+1)//2*W-(H-1)//2*W,(W+1)//2*H-(W-1)//2*H)
        if A == (H+1)//2*W-(H-1)/2*W:
            return [(H+1)//2*W,(H-1)//2*W]
        else:
            return [(W+1)//2*H,(W-1)//2*H]
Ans = H*W
for i in range(1,H):
    A1 = W*i
    S = HW(H-i,W)
    S.append(A1)
    Ans = min(Ans,abs(max(S)-min(S)))
for j in range(1,W):
    A1 = H*j
    S = HW(H,W-j)
    S.append(A1)
    Ans = min(Ans,abs(max(S)-min(S)))
print(Ans)

Solution (Python):
def solve(H,W):
    p1 = [H//3*W, (H-H//3)*(W//2), (H-H//3)*(W-W//2)]
    p2 = [ceil(H/3)*W, (H-ceil(H/3))*(W//2), (H-ceil(H/3))*(W-W//2)]
    S1 = max(p1)-min(p1)
    S2 = max(p2)-min(p2)
    S3 = 0 if H%3==0 else W
    return min(S1,S2,S3)

from math import ceil
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

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

"""
1. 1回目の割れ目をタテヨコ1かいどこかにいれる。
2. 残りは2つに別れたチョコの面積大きい方を極力2分割する。
   その時、両辺とも奇数の場合は、最小でも短辺分の長さの差が生まれる。
2の操作はO(1)で実施できるため、O(n)で実行可能であるから、
この問題に対して十分高速である。
"""

def split_choco(h, w):
    if h > w:
        h, w = w, h
    if h*w%2 == 0:
        return h*w//2, h*w//2
    else:
        assert w%2==1
        w1 = w//2
        w2 = w//2+1
        return h*w2, h*w1


ans = float('inf')
for i in range(1, H//2+1):
    large = (H-i, W)
    choco = [i*W] + list(split_choco(*large))
    ans = min(ans, max(choco)-min(choco))

for i in range(1, W//2+1):
    large = (H, W-i)
    choco = [i*H] + list(split_choco(*large))
    ans = min(ans, max(choco)-min(choco))
print(ans)

Solution (Python):
def main():
    H, W = map(int,input().split())
    area = H * W
    ans = 10**10
    
    for i in range(W//3,W//3+2):
        for j in range(W//3,W//3+2):
            areas = [H*i,H*(W-j-i),H*j]
            ans = min(ans,max(areas)-min(areas))
    
    for i in range(H//3, H//3+2):
        for j in range(H//3,H//3+2):
            areas = [W*i, W*(H-i-j), W*j]
            ans = min(ans, max(areas)-min(areas))
    
    
    for i in range(W//3,W//3+2):
        areas = [H*i]
        w_remain = W - i
        for j in range(H//2,H//2+2):
            h_remain = H - j 
            areas.append(w_remain * j)
            areas.append(w_remain * h_remain)
            ans = min(ans, max(areas)-min(areas))
    
    
    for i in range(H//3,H//3+1):
        areas = [W*i]
        h_remain = H - i
        for j in range(W//2, W//2+2):
            w_remain = W - j
            areas.append(h_remain * j)
            areas.append(h_remain * w_remain)
            ans = min(ans, max(areas)-min(areas))


    print(ans)

main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=max(h,w)
    y=min(h,w)
    ans=y
    for hi in range(1,h):
        M=max(hi*w,(h-hi)*((w+1)//2),(h-hi)*(w//2))
        m=min(hi*w,(h-hi)*((w+1)//2),(h-hi)*(w//2))
        ans=min(ans,M-m)
    for wi in range(1,w):
        M=max(wi*h,(w-wi)*((h+1)//2),(w-wi)*(h//2))
        m=min(wi*h,(w-wi)*((h+1)//2),(w-wi)*(h//2))        
        ans=min(ans,M-m)
    print(ans)

Solution (Python):
def main():
    H, W = map(int, input().split())
    ans = float('inf')
    h1, h2, h3 = 0,0,0
    w1,w2,w1 = 0,0,0
    
    h1 = H // 3
    h2 = H // 3
    h3 = H // 3
    if H % 3 == 1:
        h3 += 1
    elif H % 3 == 2:
        h2 += 1
        h3 += 1
    S = [h1*W,h2*W,h3*W]
    ans = min(max(S)-min(S),ans)
    
    h1 = H // 2
    h2 = H // 2
    h3 = H
    if H % 2 == 1:
        h2 += 1
    for w in range(1,W):
        S = [h1*(W-w),h2*(W-w),h3*w]
        ans = min(max(S)-min(S),ans)
    
    w1 = W // 3
    w2 = W // 3
    w3 = W // 3
    if W % 3 == 1:
        w3 += 1
    elif W % 3 == 2:
        w2 += 1
        w3 += 1
    S = [w1*H,w2*H,w3*H]
    ans = min(max(S)-min(S),ans)

    
    w1 = W // 2
    w2 = W // 2
    w3 = W
    if W % 2 == 1:
        w2 += 1
    for h in range(1,H):
        S = [w1*(H-h),w2*(H-h),w3*h]
        ans = min(max(S)-min(S),ans)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def get_min(h, w):
    res = float("inf")
    for i in range(1, h):
        up = [w // 2 * i, (w - w // 2) * i, w * (h - i)]
        res = min(res, max(up) - min(up))
        down = [w * i, w // 2 * (h - i), w - (w - w // 2) * (h - i)]
        res = min(res, max(down) - min(down))
    return res


H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()

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

Solution (Python):
import sys

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

ans=10**10

S=[]

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


for h1 in [h//3,(h//3)+1]:
  if ((h-h1)*w)%2==0:
    S.append([h1*w,((h-h1)*w)//2,((h-h1)*w)//2])
  else:
    S.append([h1*w,((h-h1)//2)*w,((h-h1)//2+1)*w])
    S.append([h1*w,(w//2)*(h-h1),(w//2+1)*(h-h1)])

for w1 in [w//3,(w//3)+1]:
  if ((w-w1)*h)%2==0:
    S.append([w1*h,((w-w1)*h)//2,((w-w1)*h)//2])
  else:
    S.append([w1*h,((w-w1)//2)*h,((w-w1)//2+1)*h])
    S.append([w1*h,(h//2)*(w-w1),(h//2+1)*(w-w1)])

for si in S:
  ans=min(ans,max(si)-min(si))

print(ans)

Solution (Python):
def Type_1(H,W):
    A=H//3
    B=(H+2)//3
    return (B-A)*W

def Type_2(H,W):
    M=float("inf")
    for x in range(1,H):
        P=x*W
        Q=(H-x)*(W>>1)
        M=min(M,max(P,Q,H*W-(P+Q))-min(P,Q,H*W-(P+Q)))
    return M

def Type_Merge(H,W):
    X=Type_1(H,W)
    Y=Type_2(H,W)
    return min(X,Y)

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

print(min(Type_Merge(H,W),Type_Merge(W,H)))

Solution (Python):
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    h, w = ns()

    ans = INF
    for i in range(1, h):
        area1 = w * i
        remain_h = h - i
        area2a = [area1]
        odd = w % 2
        area2a.append(remain_h * (w // 2))
        area2a.append(remain_h * ((w + odd) // 2))
        ans = min(ans, max(area2a) - min(area2a))

        if remain_h >= 2:
            area2b = [area1]
            odd = remain_h % 2
            area2b.append((remain_h // 2) * w)
            area2b.append(((remain_h + odd) // 2 )* w)
            ans = min(ans, max(area2b) - min(area2b))

    w, h = h, w
    for i in range(1, h):
        area1 = w * i
        remain_h = h - i
        area2a = [area1]
        odd = w % 2
        area2a.append(remain_h * (w // 2))
        area2a.append(remain_h * ((w + odd) // 2))
        ans = min(ans, max(area2a) - min(area2a))

        if remain_h >= 2:
            area2b = [area1]
            odd = remain_h % 2
            area2b.append((remain_h // 2) * w)
            area2b.append(((remain_h + odd) // 2 )* w)
            ans = min(ans, max(area2b) - min(area2b))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h, w =map(int, input().split())
ch1 = h//3
ch2 = ch1+1
cw1 = w//3
cw2 = cw1+1
ans = float('inf')


s = [0,0,0]
s[0]=ch1*w
yoko1 = w//2
yoko2 = w-yoko1
s[1]=(h-ch1)*yoko1
s[2]=(h-ch1)*yoko2
temp = max(s)-min(s)
ans = min(ans, temp)

s = [0,0,0]
s[0]=ch2*w
yoko1 = w//2
yoko2 = w-yoko1
s[1]=(h-ch2)*yoko1
s[2]=(h-ch2)*yoko2
temp = max(s)-min(s)
ans = min(ans, temp)

s = [0,0,0]
s[0]=ch1*w
tate1=(h-ch1)//2
tate2=h-ch1-tate1
s[1]=tate1*w
s[2]=tate2*w
temp = max(s)-min(s)
ans = min(ans, temp)


s = [0,0,0]
s[0]=cw1*h
yoko1=(w-cw1)//2
yoko2=w-cw1-yoko1
s[1]=yoko1*h
s[2]=yoko2*h
temp = max(s)-min(s)
ans = min(ans, temp)


s = [0,0,0]
s[0]=cw1*h
tate1 = h//2
tate2 = h-tate1
s[1]=(w-cw1)*tate1
s[2]=(w-cw1)*tate2
temp = max(s)-min(s)
ans = min(ans, temp)


s = [0,0,0]
s[0]=cw2*h
tate1 = h//2
tate2 = h-tate1
s[1]=(w-cw2)*tate1
s[2]=(w-cw2)*tate2
temp = max(s)-min(s)
ans = min(ans, temp)


print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()

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

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

if __name__ == '__main__':
    resolve()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  ans=[]

  h1=h//3
  h2=(h-h1)//2
  h3=h-(h1+h2)
  ans.append(max(h1,h2,h3)*w-min(h1,h2,h3)*w)

  w1=w//3
  w2=(w-w1)//2
  w3=w-(w1+w2)
  ans.append(max(w1,w2,w3)*h-min(w1,w2,w3)*h)

  mn=inf
  for i in range(1,h):
    a1=w*i
    w1=w//2
    a2=w1*(h-i)
    w2=w-w1
    a3=w2*(h-i)
    mn=min(mn,max(a1,a2,a3)-min(a1,a2,a3))
  ans.append(mn)

  mn=inf
  for i in range(1,w):
    a1=h*i
    h1=h//2
    a2=h1*(w-i)
    h2=h-h1
    a3=h2*(w-i)
    mn=min(mn,max(a1,a2,a3)-min(a1,a2,a3))
  ans.append(mn)

  return min(ans)


print(main())

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

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

Dif = 100000000

for i in range (1, min(H//2+2, H)):
	for j in range (max(1, W//2-2), min(W, W//2+3)):
		A = i*W
		B = (H-i)*j
		C = (H-i)*(W-j)
		D = max(A, B, C) - min(A, B, C)
		if Dif > D:
			Dif = D

for i in range (1, min(W//2+2, W)):
	for j in range (max(1, H//2-2), min(H, H//2+3)):
		A = i*H
		B = (W-i)*j
		C = (W-i)*(H-j)
		D = max(A, B, C) - min(A, B, C)
		if Dif > D:
			Dif = D      

for i in range (1, min(W//3+1, W)):
	A = i*H
	B = ((W-i)//2)*H
	C = W*H-A-B
	D = max(A, B, C) - min(A, B, C)
	if Dif > D:
		Dif = D                  
            
for i in range (1, min(H//3+1, H)):
	A = i*W
	B = ((H-i)//2)*W
	C = W*H-A-B
	D = max(A, B, C) - min(A, B, C)
	if Dif > D:
		Dif = D       
            
print(Dif)

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






ans=(10**5)*(10**5)
for x in range(1,w):
    tmp=[x*h,(w-x)*(h//2),(w-x)*(h-(h//2))]
    ans=min(ans,max(tmp)-min(tmp))
    
    if w-x>=2:
        tmp=[x*h,((w-x)//2)*h,((w-x)-(w-x)//2)*h]
        ans=min(ans,max(tmp)-min(tmp))
    







for y in range(1,h):
    tmp=[y*w,(h-y)*(w//2),(h-y)*(w-w//2)]
    ans=min(ans,max(tmp)-min(tmp))

    if h-y>=2:
        tmp=[y*w,((h-y)//2)*w,((h-y)-(h-y)//2)*w]
        ans=min(ans,max(tmp)-min(tmp))
    

print(ans)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def max_diff(*A):
    return max(A)-min(A)


def _solve(H, W):
    
    min_diff = math.inf
    for h in range(1, H):
        min_diff = min(min_diff, max_diff(W*h, (W//2)*(H-h), (W-W//2)*(H-h)),
                                 max_diff(W*h, ((H-h)//2)*W, (H-h-(H-h)//2)*W))
    return min_diff


def solve():
    H, W = read_ints()
    return min(_solve(H, W), _solve(W, H))


if __name__ == '__main__':
    print(solve())

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

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

ans = min(w,h)

for hi in range(1,h):
    top = hi*w
    bottom_big = (h-hi)*((w+1)//2)
    bottom_small = (h-hi)*(w//2)
    smax = max(top,bottom_big)
    smin = min(top,bottom_small)
    ans = min(ans, smax-smin)


for wi in range(1,w):
    top = wi*h
    bottom_big = (w-wi)*((h+1)//2)
    bottom_small = (w-wi)*(h//2)
    smax = max(top,bottom_big)
    smin = min(top,bottom_small)
    ans = min(ans, smax-smin)

print(ans)

Solution (Python):
from math import floor, ceil


def result_dividing_by_a_direction(x, y, is_ceil):
    new_x = floor(x / 3)
    if is_ceil:
        new_x = ceil(x / 3)
    return abs(new_x - (x - 2 * new_x)) * y


def result_dividing_2plus1(x, y, d):
    area1 = x * d
    area2 = (y - d) * (x // 2)
    area3 = (y - d) * (x - (x // 2))
    return max(area1, area2, area3) - min(area1, area2, area3)


def main():
    h, w = map(int, input().split())
    ans = h * w
    for i in range(2):
        ans = result_dividing_by_a_direction(h, w, i)
        ans = min(result_dividing_by_a_direction(w, h, i), ans)
    for d in range(1, w):
        ans = min(result_dividing_2plus1(h, w, d), ans)
    for d in range(1, h):
        ans = min(result_dividing_2plus1(w, h, d), ans)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from math import ceil
h, w = map(int, input().split())
def solve(h, w):
    ans = float("inf")
    for i in range(1, h):
        l = [i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)]
        l2 = [i * w, ((h - i) // 2) * w, (ceil((h - i) / 2)) * w]
        ans = min(ans, max(l) - min(l), max(l2) - min(l2))
    return ans
print(min(solve(h, w), solve(w, h)))

Solution (Python):
import sys

input = sys.stdin.readline


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

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

    q, r = divmod(W, 2)
    W_1 = q
    W_2 = q + r
    for y in range(1, H):
        S_1 = y * W
        S_2 = (H - y) * W_1
        S_3 = (H - y) * W_2
        S_max = max(S_1, S_2, S_3)
        S_min = min(S_1, S_2, S_3)
        ans = min(ans, S_max - S_min)

    q, r = divmod(H, 2)
    H_1 = q
    H_2 = q + r
    for x in range(1, W):
        S_1 = x * H
        S_2 = (W - x) * H_1
        S_3 = (W - x) * H_2
        S_max = max(S_1, S_2, S_3)
        S_min = min(S_1, S_2, S_3)
        ans = min(ans, S_max - S_min)

    print(ans)


if __name__ == "__main__":
    main()

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

ans = float("inf")
for i in range(h):
    p1 = i * w
    p2 = ((h - i) // 2) * w
    p3 = (h - i - ((h - i) // 2)) * w

    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

    p1 = i * w
    p2 = (h - i) * (w // 2)
    p3 = (h - i) * (w - (w // 2))

    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

w, h = h, w
for i in range(h):
    p1 = i * w
    p2 = ((h - i) // 2) * w
    p3 = (h - i - ((h - i) // 2)) * w

    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

    p1 = i * w
    p2 = (h - i) * (w // 2)
    p3 = (h - i) * (w - (w // 2))

    ans = min(ans, max(p1, p2, p3) - min(p1, p2, p3))

print(ans)

Solution (Python):
from math import *
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
    exit()
t=h*w/3
a=[floor(w/3),ceil(w/3)]
b=[floor(h/2),ceil(h/2)]
c=[floor(h/3),ceil(h/3)]
d=[floor(w/2),ceil(w/2)]
ans=float("inf")
for i in a:
    for j in b:
        a1=i*h
        a2=j*(w-i)
        a3=(h-j)*(w-i)
        tmp=max(abs(a1-a2),abs(a1-a3),abs(a3-a2))
        if tmp<ans:
            ans=tmp
for i in c:
    for j in d:
        a1=w*i
        a2=(h-i)*j
        a3=(w-j)*(h-i)
        tmp=max(abs(a1-a2),abs(a1-a3),abs(a3-a2))
        if tmp<ans:
            ans=tmp
for i in a:
    a1=i*h
    a2=i*h
    a3=h*w-a1-a2
    tmp=max(abs(a1-a2),abs(a1-a3),abs(a3-a2))
    if tmp<ans:
        ans=tmp
for i in c:
    a1=i*w
    a2=i*w
    a3=h*w-a1-a2
    tmp=max(abs(a1-a2),abs(a1-a3),abs(a3-a2))
    if tmp<ans:
        ans=tmp
print(ans)

Solution (Python):
def f(h, w):
    t = pow(10,9)
    for hi in range(1,h):
        a = hi*w
        b = (h-hi)*(w//2)
        c = (h-hi)*(w-w//2)
        t = min(t, max([a,b,c])-min([a,b,c]))
        b = ((h-hi)//2)*w
        c = ((h-hi)-(h-hi)//2)*w
        t = min(t, max([a,b,c])-min([a,b,c]))
    return t

h, w = map(int, input().split())
print(min(f(h,w), f(w,h)))

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

def main():
    if H % 3 == 0 or W % 3 == 0:
        return 0
    total = H * W
    ans = 10 ** 20
    for i in range(W):
        one = H * (i+1)
        two = (W-(i+1)) * (H//2)
        three = total - one - two
        ans = min(ans, max([one, two, three]) - min([one, two, three]))
        two = (W-(i+1))//2 * H
        three = total - one - two
        ans = min(ans, max([one, two, three]) - min([one, two, three]))
        two = (W-(i+1))//2 * H
    return ans

ret = main()
H, W = W, H
ret2 = main()
print(min(ret, ret2))

Solution (Python):
H,W = map(int,input().split())
cmin = H*W
if H%3==0 or W%3==0:
    ans = 0
else:
    for i in range(H-1):
        s1 = W*(i+1)
        t = H-i-1
        s2 = W*(t//2)
        s3 = W*(t-t//2)
        d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
        cmin = min(cmin,d)
        t1 = W//2
        s2 = t*t1
        s3 = t*(W-t1)
        d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
        cmin = min(cmin,d)
    for j in range(W-1):
        s1 = H*(j+1)
        t = W-j-1
        s2 = H*(t//2)
        s3 = H*(t-t//2)
        d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
        cmin = min(cmin,d)
        t1 = H//2
        s2 = t*t1
        s3 = t*(H-t1)
        d = max(abs(s1-s2),abs(s2-s3),abs(s3-s1))
        cmin = min(cmin,d)
    ans = cmin
print(ans)

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

ans = 10**18
for i in range(1, h):
    s1 = w*i
    if i != h-1:
        s2 = ((h-i)//2)*w
        s3 = (h-(h-i)//2-i)*w
        d1 = max([s1, s2, s3])-min([s1, s2, s3])
        s2 = (h-i)*(w//2)
        s3 = (h-i)*(w-w//2)
        d2 = max([s1, s2, s3])-min([s1, s2, s3])
        ans = min(ans, min(d1, d2))
    else:
        s2 = (h-i)*(w//2)
        s3 = (h-i)*(w-w//2)
        d2 = max([s1, s2, s3])-min([s1, s2, s3])
        ans = min(ans, d2)

for i in range(1, w):
    s1 = h*i
    if i != w-1:
        s2 =  ((w-i)//2)*h
        s3 = (w-(w-i)//2-i)*h
        d1 = max([s1, s2, s3])-min([s1, s2, s3])
        s2 = (w-i)*(h//2)
        s3 = (w-i)*(h-h//2)
        d2 = max([s1, s2, s3])-min([s1, s2, s3])
        ans = min(ans, min(d1, d2))
    else:
        s2 = (w-i)*(h//2)
        s3 = (w-i)*(h-h//2)
        d2 = max([s1, s2, s3])-min([s1, s2, s3])
        ans = min(ans, d2)
print(ans)

Solution (Python):
def solve():
  ans = float('inf')
  H, W = map(int, input().split())
  for h in range(1,H):
    o1 = (H-h)//2*W
    o2 = (H-h)*W-o1
    a = [h*W,o1,o2]
    ans = min(ans,max(a)-min(a))
    o1 = W//2*(H-h)
    o2 = (H-h)*W-o1
    a = [h*W,o1,o2]
    ans = min(ans,max(a)-min(a))
  for w in range(1,W):
    o1 = (W-w)//2*H
    o2 = (W-w)*H-o1
    a = [w*H,o1,o2]
    ans = min(ans,max(a)-min(a))
    o1 = H//2*(W-w)
    o2 = (W-w)*H-o1
    a = [w*H,o1,o2]
    ans = min(ans,max(a)-min(a))
  return ans
print(solve())

Solution (Python):
def solve():
  ans = float('inf')
  H, W = map(int, input().split())
  for h in range(1,H):
    o1 = (H-h)//2*W
    o2 = (H-h)*W-o1
    a = [h*W,o1,o2]
    ans = min(ans,max(a)-min(a))
    o1 = W//2*(H-h)
    o2 = (H-h)*W-o1
    a = [h*W,o1,o2]
    ans = min(ans,max(a)-min(a))
  for w in range(1,W):
    o1 = (W-w)//2*H
    o2 = (W-w)*H-o1
    a = [w*H,o1,o2]
    ans = min(ans,max(a)-min(a))
    o1 = H//2*(W-w)
    o2 = (W-w)*H-o1
    a = [w*H,o1,o2]
    ans = min(ans,max(a)-min(a))
  return ans
print(solve())

Solution (Python):
H,W = map(int,input().split())
ans = 1000000000000
if H >= 3:
    if H % 3 == 0:
        ans = 0
    else:
        ans = min(ans,W)
if W >= 3:
    if W % 3 == 0:
        ans = 0
    else:
        ans = min(ans,H)

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

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

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

if H > W:
    H,W = W,H
ans = 1 << 50

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


for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    
    
    S2 = w_rest * ((H-1)//2+1)
    S3 = H*W - S1 - S2
    diff1 = 1 << 50
    if S1 <= S3 <= S2:
        diff1 = S2 - S1
    
    
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    S3 = H*W - S1 - S2
    if S2 <= S3 <= S1:
        diff2 = S1 - S2
    
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3:
        diff3 = abs(S3-S2)
    mn = min(diff1,diff2,diff3)        
    ans = min(ans,mn)

H,W = W,H
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    
    
    S2 = w_rest * ((H-1)//2+1)
    S3 = H*W - S1 - S2
    diff1 = 1 << 50
    if S1 <= S3 <= S2:
        diff1 = S2 - S1
    
    
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    S3 = H*W - S1 - S2
    if S2 <= S3 <= S1:
        diff2 = S1 - S2
    
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3:
        diff3 = abs(S3-S2)
    mn = min(diff1,diff2,diff3)        
    ans = min(ans,mn)
print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ans = []
a = ((h+2)//3)*w
nh = h - (h+2)//3
b = (nh+1)//2*w
c = (nh-(nh+1)//2)*w
ans.append(max(a,b,c) - min(a,b,c))
b = nh*((w+1)//2)
c = nh*(w-(w+1)//2)
ans.append(max(a,b,c) - min(a,b,c))
a = h*((w+2)//3)
nw = w - (w+2)//3
b = (h+1)//2*nw
c = (h-(h+1)//2)*nw
ans.append(max(a,b,c) - min(a,b,c))
b = h*((nw+1)//2)
c = h*(nw-(nw+1)//2)
ans.append(max(a,b,c) - min(a,b,c))

a = ((h)//3)*w
nh = h - (h)//3
b = (nh+1)//2*w
c = (nh-(nh+1)//2)*w
ans.append(max(a,b,c) - min(a,b,c))
b = nh*((w+1)//2)
c = nh*(w-(w+1)//2)
ans.append(max(a,b,c) - min(a,b,c))
a = h*((w)//3)
nw = w - (w)//3
b = (h+1)//2*nw
c = (h-(h+1)//2)*nw
ans.append(max(a,b,c) - min(a,b,c))
b = h*((nw+1)//2)
c = h*(nw-(nw+1)//2)
ans.append(max(a,b,c) - min(a,b,c))

a = ((h+2)//3)*w
nh = h - (h+2)//3
b = (nh)//2*w
c = (nh-(nh)//2)*w
ans.append(max(a,b,c) - min(a,b,c))
b = nh*((w)//2)
c = nh*(w-(w)//2)
ans.append(max(a,b,c) - min(a,b,c))
a = h*((w+2)//3)
nw = w - (w+2)//3
b = (h)//2*nw
c = (h-(h)//2)*nw
ans.append(max(a,b,c) - min(a,b,c))
b = h*((nw)//2)
c = h*(nw-(nw)//2)
ans.append(max(a,b,c) - min(a,b,c))

a = ((h)//3)*w
nh = h - (h)//3
b = (nh)//2*w
c = (nh-(nh)//2)*w
ans.append(max(a,b,c) - min(a,b,c))
b = nh*((w)//2)
c = nh*(w-(w)//2)
ans.append(max(a,b,c) - min(a,b,c))
a = h*((w)//3)
nw = w - (w)//3
b = (h)//2*nw
c = (h-(h)//2)*nw
ans.append(max(a,b,c) - min(a,b,c))
b = h*((nw)//2)
c = h*(nw-(nw)//2)
ans.append(max(a,b,c) - min(a,b,c))
print(min(ans))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

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


def f(h,w):
    ans = h*w
    for i in range(1,h):
        v1 = i*w
        if (h-i)%2==0 or w%2 == 0:
            v2 = (h-i)*w//2
        else:
            v2 = max((h-i)//2*w,w//2*(h-i))
        v3 = (h-i)*w - v2
        
        ans = min(ans,max(v1,v2,v3)-min(v1,v2,v3))
        
    return ans

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

Solution (Python):
def main():
    H, W = list(map(int, input().split()))
    ww = W // 2
    hh = H // 2
    ans = 10 ** 11
    max_min = lambda x, y, z: max(x, y, z) - min(x, y, z)
    if W % 3  == 0 or H % 3 == 0:
        print(0)
        exit()
    if H > 3:
        ans = min(ans, W)
    if W > 3:
        ans = min(ans, H)
    for h in range(1, H):
        s0 = h * W
        s1 = (H - h) * ww
        s2 = (H - h) * (W - ww)
        ans = min(ans, max_min(s0, s1, s2))
    for w in range(1, W):
        s0 = w * H
        s1 = (W - w) * hh
        s2 = (W - w) * (H - hh)
        ans = min(ans, max_min(s0, s1, s2))
    print(ans)

if __name__ == '__main__':
    main()