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:
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 1e10 
for _ in range(2):
    for i in range(1, H):
        a = i*W
        b = (W//2) * (H-i)
        c = ((W+1)//2 * (H-i))
        ans = min(ans, abs(max([a,b,c]) - min([a,b,c])))
        b = ((H-i)//2 * W)
        c = ((H-i+1)//2 * W)
        ans = min(ans, abs(max([a,b,c]) - min([a,b,c])))
    H, W = W, H

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
ans=10**10
if h>=3:
    if h%3==0:
        ans=0
    else:
        ans=min(w,ans)
if w>=3:
    if w%3==0:
        ans=0
    else:
        ans=min(h,ans)
for i in range(1,w):
    a=h*i
    if h%2==0:
        b=(w-i)*h//2
        c=b
    else:
        b=(w-i)*((h+1)//2)
        c=(w-i)*h-b
    temp=max(a,b,c)-min(a,b,c)
    ans=min(ans,temp)
for i in range(1,h):
    a=w*i
    if w%2==0:
        b=(h-i)*w//2
        c=b
    else:
        b=(h-i)*((w+1)//2)
        c=(h-i)*h-b
    temp=max(a,b,c)-min(a,b,c)
    ans=min(ans,temp)
print(ans)

Submission status: Accepted

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

m=0 if h%3==0 else w
n=0 if w%3==0 else h
m=min(m,n)
for i in range(1,w):
    s=sorted([h*i,(h//2)*(w-i),h*w-h*i-(h//2)*(w-i)])
    m=min(m,s[2]-s[0])
for i in range(1,h):
    s=sorted([w*i,(w//2)*(h-i),h*w-w*i-(w//2)*(h-i)])
    m=min(m,s[2]-s[0])
print(m)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    s1 = round(h / 3) * w
    S1 = h * round(w / 3)
    h2 = h - round(h / 3)
    w2 = w - round(w / 3)
    if h2 % 2 == 0 or w % 2 == 0:
        s2 = h2 * w // 2
        s3 = s2
    else:
        h2, w = min(h2, w), max(h2, w)
        s2 = h2 * (w // 2)
        s3 = h2 * (w // 2 + 1)
    if h % 2 == 0 or w2 % 2 == 0:
        S2 = h * w2 // 2
        S3 = S2
    else:
        h, w2 = min(h, w2), max(h, w2)
        S2 = h * (w2 // 2)
        S3 = h * (w2 // 2 + 1)
    print(min(max(s1, s2, s3) - min(s1, s2, s3), max(S1, S2, S3) - min(S1, S2, S3)))

Submission status: Accepted

Solution code:
def solve(h,w):
    ans1 = float("inf")
    ans2 = float("inf")
    for i in range(1,h):
        w_mid = w//2
        s1_max = max(i*w,(h-i)*w_mid,(h-i)*(w-w_mid))
        s1_min = min(i*w,(h-i)*w_mid,(h-i)*(w-w_mid))
        ans1 = min(ans1,s1_max - s1_min)
    for i in range(1,h):
        h_mid = (h-i)//2
        s2_max = max(i*w,h_mid*w,(h-i-h_mid)*w)
        s2_min = min(i*w,h_mid*w,(h-i-h_mid)*w)
        ans2 = min(ans2,s2_max-s2_min)
    return min(ans1,ans2)
def main():
    h,w = map(int,input().split())
    print(min(solve(h,w),solve(w,h)))
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    x, y = LI()
    a = [1, 3, 5, 7, 8, 10, 12]
    b = [4, 6, 9, 11]
    c = [2]
    if x in a and y in a:
        print("Yes")
        return
    if x in b and y in b:
        print("Yes")
        return
    if x in c and y in c:
        print("Yes")
        return
    print("No")
    return

#B
def B():
    h, w = LI()
    print("#" * (w + 2))
    for _ in range(h):
        a = ["#"]
        for s in S():
            a.append(s)
        a.append("#")
        print("".join(a))
    print("#" * (w + 2))
    return

#C
def C():
    h, w = LI()
    ans = inf
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    h, w = w, h
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    print(ans)
    return

#D
def D():
    return


#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
import math

def main(H,W):
    ans = float('inf')
    w = math.floor(W / 2)
    for i in range(H):
        Smin = min(i * W, w * (H - i), (W - w) * (H - i))
        Smax = max(i * W, w * (H - i), (W - w) * (H - i))
        ans = min(ans, Smax-Smin)
    return min(H,ans)

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

Submission status: Accepted

Solution code:
#最初の分割を全探索
H,W = map(int,input().split())
ans = H*W
for i in range(1,H):
    S0 = i*W
    h = (H-i)//2
    S1 = [S0,h*W,(H-i-h)*W]
    ans = min(ans,max(S1)-min(S1))
    h = H-i
    w = W//2
    S1 = [S0,h*w,h*(W-w)]
    ans = min(ans,max(S1)-min(S1))
for j in range(1,W):
    S0 = j*H
    w = (W-j)//2
    S1 = [S0,H*w,H*(W-j-w)]
    ans = min(ans,max(S1)-min(S1))
    w = W-j
    h = H//2
    S1 = [S0,h*w,(H-h)*w]
    ans = min(ans,max(S1)-min(S1))
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)

"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
x,y = ips()

if x%3==0 or y%3 == 0:
    print(0)
    exit(0)
ans = min(x,y)
base = [y,y//2,y//2]
if y%2:base[2]+=1
total = [0,x*base[1],x*base[2]]
ans = min(ans,max(total)-min(total))
for i in range(x):
    total[0]+=y
    total[1]-=base[1]
    total[2]-=base[2]
    ans = min(ans,max(total)-min(total))

base = [x,x//2,x//2]
if x%2:base[2]+=1
total = [0,y*base[1],y*base[2]]
ans = min(ans,max(total)-min(total))
for i in range(y):
    total[0]+=x
    total[1]-=base[1]
    total[2]-=base[2]
    ans = min(ans,max(total)-min(total))
print(ans)

Submission status: Accepted

Solution code:
def f(W, H):
    res = float('INF')
    w = W // 2
    for h in range(1, H):
        res = min(res, max(h * W, (H - h) * w,  (H - h) * (W - w)
                           ) - min(h * W, (H - h) * w,  (H - h) * (W - w)))
    return min(H, res)


def main():
    H, W = map(int, input().split())
    if H % 3 == 0 or W % 3 == 0:
        print(0)
    else:
        print(min(f(W, H), f(H, W)))


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC62 C

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

def solve(H,W):
    mid = math.floor(W/2)
    ans = float('inf')
    for i in range(1,H):
        Smin = min(i*W,mid*(H-i),(W-mid)*(H-i))
        Smax = max(i*W,mid*(H-i),(W-mid)*(H-i))
        ans = min(ans,Smax-Smin)
    return min(ans,H)
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    print(min(solve(h,w),solve(w,h)))

Submission status: Accepted

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

ans_wsplit = [max(abs((i * w) - (((h - i) + 1) // 2) * w), abs((i * w) - ((h - i) // 2) * w)) for i in range(1, h)]
ans_hsplit = [max(abs((i * h) - (((w - i) + 1) // 2) * h), abs((i * h) - ((w - i) // 2) * h)) for i in range(1, w)]

ans_wline = [max(abs((i * w) - ((w + 1) // 2) * (h - i)), abs((i * w) - (w // 2) * (h - i))) for i in range(1, h)]
ans_hline = [max(abs((i * h) - ((h + 1) // 2) * (w - i)), abs((i * h) - (h // 2) * (w - i))) for i in range(1, w)]

print(min(ans_wsplit + ans_hsplit + ans_wline + ans_hline))

Submission status: Accepted

Solution code:
import math
def calc(h, w):
    case1 = (0 if h % 3 == 0 else h)
    mid = math.floor(w/2)
    case2 = float("inf")
    for i in range(1, h):
        Smin = min(i*w, mid*(h-i), (w-mid)*(h-i))
        Smax = max(i*w, mid*(h-i), (w-mid)*(h-i))
        case2 = min(Smax-Smin, case2)
    return min(case1, case2)
H, W = map(int, input().split())
print(min(calc(H,W), calc(W,H)))

Submission status: Accepted

Solution code:

def main():
    high, width = map(int, input().split())
    ans = high * width

    for i in range(1, high):
        a = i * width

        b1 = (high - i) * (width // 2)
        c1 = high * width - a - b1

        b2 = ((high - i) // 2) * width
        c2 = high * width - a - b2

        kari = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2))

        ans = min(ans, kari)

    for i in range(1, width):
        a = i * high

        b1 = (width - i) * (high // 2)
        c1 = high * width - a - b1

        b2 = ((width - i) // 2) * high
        c2 = high * width - a - b2

        kari = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2))

        ans = min(ans, kari)


    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
MIN = 10**11
S1 = 0
S2 =  0
S3 = 0
if H%3 == 0 or W %3==0:
    print(0)
else:
    for i in range(1,H):
        S1 = i * W
        S2 = (H-i)*(W//2)
        S3 = (H-i)*(W - W//2)
        MIN = min(MIN, max(S1,S2,S3)- min(S1,S2,S3))
        
    for i in range(1,W):
        S1 = i * H
        S2 = (W-i)*(H//2)
        S3 = (W-i)*(H - H//2)
        MIN = min(MIN, max(S1,S2,S3)- min(S1,S2,S3))
        
    for i in range(1,H):
        S1 = i*W
        S2 = ((H-i)//2)*W
        S3 = H*W - S1-S2
        MIN = min(MIN, max(S1,S2,S3)- min(S1,S2,S3))
    
    for i in range(1,H):
        S1 = i*H
        S2 = ((W-i)//2) *H
        S3 = H*W - S1-S2
        MIN = min(MIN, max(S1,S2,S3)- min(S1,S2,S3))
        
    print(MIN)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))

# 縦3等分、横3等分、縦2・横1、横1・縦2
ans = IINF
# 縦
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)
# 縦2、横1
w = 1
while w < W:
    a = (W - w) * H
    b = w * (H // 2)
    c = w * H - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
    w += 1
# 縦1、横2
h = 1
while h < H:
    a = (H - h) * W
    b = h * (W // 2)
    c = h * W - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
    h += 1
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=10**9
if H%3==0 or W%3==0:
    ans=0
else:
    if ans>H or ans>W:
        ans=min(H,W)
for i in range(H):
    a=(i+1)*W
    if W%2==0:
        b=(H-(i+1))*(W//2)
        c=(H-(i+1))*(W//2)
    else:
        b=(H-(i+1))*(W//2)
        c=(H-(i+1))*((W//2)+1)
    if ans>(max(a,b,c)-min(a,b,c)):
        ans=(max(a,b,c)-min(a,b,c))
W,H=H,W
for i in range(H):
    a=(i+1)*W
    if W%2==0:
        b=(H-(i+1))*(W//2)
        c=(H-(i+1))*(W//2)
    else:
        b=(H-(i+1))*(W//2)
        c=(H-(i+1))*((W//2)+1)
    if ans>(max(a,b,c)-min(a,b,c)):
        ans=(max(a,b,c)-min(a,b,c))
print(ans)

Submission status: Accepted

Solution code:

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


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

else:

    ans = float("inf")
    A = 0
    B = 0
    C = 0

    # W方向から切る場合

    ## 1/3より少し小さく切る

    A = (W//3) * H

    B = (W - (W//3)) * (H // 2)
    C = W*H - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )

    B = ((W - (W//3)) // 2 ) * H
    C = W*H - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )

    A = (W//3 + 1) * H
    B = (W - (W//3 + 1)) * (H//2)
    C = (W*H) - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )

    newH = W
    newW = H

    H = newH
    W = newW

    A = (W//3) * H

    B = (W - (W//3)) * (H // 2)
    C = W*H - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )

    B = ((W - (W//3)) // 2 ) * H
    C = W*H - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )

    A = (W//3 + 1) * H
    B = (W - (W//3 + 1)) * (H//2)
    C = (W*H) - (A+B)

    ans = min( ans , max(A,B,C)-min(A,B,C) )


    print (ans)

Submission status: Accepted

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

for i in range(1,h-1):
    nokori=h-i
    two=nokori//2
    three=nokori-two
    if two==0 or three==0:
        continue
    ans=min(ans,max(i*w, two*w, three*w)-min(i*w, two*w, three*w))

for i in range(1,h):
    nokori=h-i
    two=w//2
    three=w-two
    if two==0 or three==0:
        continue
    ans=min(ans,max(i*w, nokori*two, nokori*three)-min(i*w, nokori*two, nokori*three))

tmp=w
w=h
h=tmp
# print(w)
# print(h)

for i in range(1,h-1):
    nokori=h-i
    two=nokori//2
    three=nokori-two
    if two==0 or three==0:
        continue
    ans=min(ans,max(i*w, two*w, three*w)-min(i*w, two*w, three*w))

for i in range(1,h):
    nokori=h-i
    two=w//2
    three=w-two
    if two==0 or three==0:
        continue
    # print(i*w)
    # print(nokori*two)
    # print(nokori*three)
    # print()
    ans=min(ans,max(i*w, nokori*two, nokori*three)-min(i*w, nokori*two, nokori*three))

print(ans)

Submission status: Accepted

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

def sub(a,k,b,l):
    list = sorted([a*l,(k-a)*b,(k-a)*(l-b)])
    return list[2]-list[0]

if H*W % 3 == 0:
    print(0)
else:
    a = W//3
    b = H//2
    g1 = 99999999999999999999999999
    for i in [a,a+1]:
        if H%2==0:
            g1 = min(g1,sub(i,W,H//2,H))
        for j in [b,b+1]:
            g1 = min(g1,sub(i,W,j,H))

    c = H//3
    d = W//2
    g2 = 99999999999999999999999999
    for i in [c,c+1]:
        if W%2==0:
            g2 = min(g2,sub(i,H,W//2,W))
        for j in [b,b+1]:
            g2 = min(g2,sub(i,H,j,W))
    print(min(g1,g2,H,W))

Submission status: Accepted

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

if h %3 == 0 or w%3 == 0:
    print(0)
elif h == 1 or w == 1:
    print(1)
else:
    s1 = round(h / 3)*w
    h1 = h - round(h/3)
    if w % 2 == 0 or h1 % 2 == 0:
        s2 = h1*w//2
        s3 = s2
    else:
        s2 = max(w, h1)//2 * min(w, h1)
        s3 = h1*w-s2
    ans = max([s1, s2, s3])-min([s1, s2, s3])
    s1 = round(w / 3)*h
    w1 = w - round(w/3)
    if w1 % 2 == 0 or h % 2 == 0:
        s2 = h*w1//2
        s3 = s2
    else:
        s2 = max(w1, h)//2 * min(w1, h)
        s3 = h*w1-s2
    ans = min(max([s1, s2, s3])-min([s1, s2, s3]), ans)
    print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
if H*W%3==0:print(0)
else:
    a,b,c=(W//3)*H,(H//2)*(W-W//3),(H-H//2)*(W-W//3)
    H1=max(a,b,c)-min(a,b,c)
    d,e,f=((W//3)+1)*H,(H//2)*(W-(W//3)-1),(H-H//2)*(W-(W//3)-1)
    H2=max(d,e,f)-min(d,e,f)
    p,q,r=(H//3)*W,(W//2)*(H-H//3),(W-W//2)*(H-H//3)
    W1=max(p,q,r)-min(p,q,r)
    s,t,u=((H//3)+1)*W,(W//2)*(H-(H//3)-1),(W-W//2)*(H-(H//3)-1)
    W2=max(s,t,u)-min(s,t,u)
    print(min(H1,H2,W1,W2,H,W))

Submission status: Accepted

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

tmp = 999999999999999


def calc_area(H, W):
    piece_1 = i * W
    piece_2 = int(W / 2) * (H - i)
    piece_3 = int(W / 2 + 0.9) * (H - i)
    holi = max(piece_1, piece_2, piece_3) - min(piece_1, piece_2, piece_3)

    piece_2 = W * int((H - i) / 2)
    piece_3 = W * int((H - i) / 2 + 0.9)
    ver = max(piece_1, piece_2, piece_3) - min(piece_1, piece_2, piece_3)
    return min(tmp, holi, ver)


for i in range(0, H + 1):
    holi = calc_area(H, W)
    ver =  calc_area(W, H)
    tmp = min(tmp, holi, ver)


for i in range(0, W + 1):
    holi = calc_area(H, W)
    ver =  calc_area(W, H)
    tmp = min(tmp, holi, ver)

print(tmp)

Submission status: Accepted

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

def calc(h, w):
    h1 = round(h / 3)
    h2 = (h - h1) // 2
    h3 = h - h1 - h2
    hr = h2 + h3
    w1 = w // 2
    w2 = w - w1

    harr = [h1 * w, h2 * w, h3 * w]
    warr = [h1 * w, hr * w1, hr * w2]
    a = max(harr) - min(harr) if h2 else float('inf')
    b = max(warr) - min(warr) if w1 else float('inf')

    return min(a, b)

def main():
    print(min(calc(H, W), calc(W, H)))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def ep(H,W,h):
    S1=h*W
    S2=(H-h)*(W//2)
    S3=(H-h)*(W-W//2)
    c1=max(S1,S2,S3)-min(S1,S2,S3)

    T1=h*W
    T2=((H-h)//2)*W
    T3=(H-h-((H-h)//2))*W
    c2=max(T1,T2,T3)-min(T1,T2,T3)

    return min(ans,c1,c2)




if H!=1:
    for h in range(1,H):
        ans=ep(H,W,h)

H,W=W,H
if H!=1:
    for h in range(1,H):
        ans=ep(H,W,h)

print(ans)

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()

min_diff = H * W
for h1 in range(1, H):
    sa = h1*W

    h2 = (H-h1) // 2
    sb = h2*W
    sc = (H - h1 - h2)*W

    diff = max(sa, sb, sc) - min(sa, sb, sc)
    min_diff = min(diff, min_diff)

    w2 = W // 2
    sb = (H - h1)*w2
    sc = (H - h1)*(W - w2)
    diff = max(sa, sb, sc) - min(sa, sb, sc)
    min_diff = min(diff, min_diff)

for w1 in range(1, W):
    sa = H*w1

    w2 = (W-w1) // 2
    sb = H*w2
    sc = H*(W - w1 - w2)

    diff = max(sa, sb, sc) - min(sa, sb, sc)
    min_diff = min(diff, min_diff)

    h2 = H // 2
    sb = (W - w1)*h2
    sc = (W - w1)*(H - h2)
    diff = max(sa, sb, sc) - min(sa, sb, sc)
    min_diff = min(diff, min_diff)

print(min_diff)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = float('inf')
for i in range(1,H):
    a = i*W
    if H-i % 2 == 0 or W % 2 == 0:
        b = (H-i)*W//2
        c = b
    else:
        b = ((H-i)*W - min(H-i,W))//2
        c = ((H-i)*W + min(H-i,W))//2
    ans = min(ans,max(a,b,c)-min(a,b,c))
H,W = W,H
for i in range(1,H):
    a = i*W
    if H-i % 2 == 0 or W % 2 == 0:
        b = (H-i)*W//2
        c = b
    else:
        b = ((H-i)*W - min(H-i,W))//2
        c = ((H-i)*W + min(H-i,W))//2
    ans = min(ans,max(a,b,c)-min(a,b,c))
if H%3 == 0 or W%3 == 0:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline

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

ans = 10 ** 9 + 7

# VVV
for x in range(1, W):
    a = H * x
    b = H * ((W - x) // 2)
    c = H * ((W - x) - (W - x) // 2)
    if a < 1 or b < 1 or c < 1: continue
    ans_tmp = max(a, b, c) - min(a, b, c)
    # print("#", (a, b, c), ans_tmp, ans)
    if ans > ans_tmp: ans = ans_tmp

# VHH
for x in range(1, W):
    a = H * x
    b = (H // 2) * (W - x)
    c = (H - (H // 2)) * (W - x)
    if a < 1 or b < 1 or c < 1: continue
    ans_tmp = max(a, b, c) - min(a, b, c)
    if ans > ans_tmp: ans = ans_tmp

# HHH
for y in range(1, H):
    a = y * W
    b = ((H - y) // 2) * W
    c = ((H - y) - (H - y) // 2) * W
    if a < 1 or b < 1 or c < 1: continue
    ans_tmp = max(a, b, c) - min(a, b, c)
    if ans > ans_tmp: ans = ans_tmp

# HVV
for y in range(1, H):
    a = y * W
    b = (H - y) * (W // 2)
    c = (H - y) * (W - (W // 2))
    if a < 1 or b < 1 or c < 1: continue
    ans_tmp = max(a, b, c) - min(a, b, c)
    if ans > ans_tmp: ans = ans_tmp

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
d = h * w
S = []
if (h % 3 == 0) or (w % 3 == 0):
    print(0)
else:
    i = 1
    a = 0
    b = 1
    while a < b:
        a = w * i
        b = ((w // 2) + (w % 2)) * (h - i)
        c = (w // 2) * (h - i)
        abc = [a, b, c]
        S += [max(abc) - min(abc)]
        i += 1

    i = 1
    a = 0
    b = 1
    while a < b:
        a = h * i
        b = ((h // 2) + (h % 2)) * (w - i)
        c = (h // 2) * (w - i)
        abc = [a, b, c]
        S += [max(abc) - min(abc)]
        i += 1

    a = h // 3
    b = (h - a) // 2
    c = h - a - b
    abc = [a * w, b * w, c * w]
    S += [max(abc) - min(abc)]

    a = w // 3
    b = (w - a) // 2
    c = w - a - b
    abc = [a * h, b * h, c * h]
    S += [max(abc) - min(abc)]
    
    print(min(S))

Submission status: Accepted

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

# ひとつは何らかの辺を完全に含む

def F(H,W):
  # 2つの場合
  # max, minを返す
  if H%2 == 0 or W%2 == 0:
    return (H*W//2, H*W//2)
  if H > W:
    H,W = W,H
  return (H*(W-1)//2, H*(W+1)//2)

answer = H*W
for h in range(1,H):
  x = [W*h]
  x += list(F(H-h,W))
  answer = min(answer, max(x) - min(x))
  
for w in range(1,W):
  x = [H*w]
  x += list(F(W-w,H))
  answer = min(answer, max(x) - min(x))
  
print(answer)

Submission status: Accepted

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

menseki = H * W
_menseki = menseki
ans = 100000000

for i in range(0, H):
    menseki -= W
    _a = W*(i+1)
    if i+1 < H:
        m = W // 2 * (H-(i+1)) # 縦切りの面積
        m2 = menseki - m
        buff_m = min(m, _a)
        buff_mx = max(m2, _a)
        # print('menseki ' + str(menseki))
        # print('m系')
        # # print(W//2, H-(i+1), m, m2)
        # print(buff_mx, buff_m, buff_mx-buff_m, ans)
        ans = min(ans, buff_mx - buff_m)

        # 横切りの面積
        _w = ((H-(i+1)) // 2) * W
        _w2 = menseki - _w
        buff_w = min(_w, _a)
        buff_w2 = max(_w2, _a)
        # print('w系')
        # print(buff_w, buff_w2, buff_w2-buff_w, ans)
        ans = min(ans, buff_w2 - buff_w)

menseki = _menseki
H, W = (W, H)

for i in range(0, H):
    menseki -= W
    _a = W*(i+1)
    if i+1 < H:
        m = W // 2 * (H-(i+1)) # 縦切りの面積
        m2 = menseki - m
        buff_m = min(m, _a)
        buff_mx = max(m2, _a)
        # print('menseki ' + str(menseki))
        # print('m系')
        # # print(W//2, H-(i+1), m, m2)
        # print(buff_mx, buff_m, buff_mx-buff_m, ans)
        ans = min(ans, buff_mx - buff_m)

        # 横切りの面積
        _w = ((H-(i+1)) // 2) * W
        _w2 = menseki - _w
        buff_w = min(_w, _a)
        buff_w2 = max(_w2, _a)
        # print('w系')
        # print(buff_w, buff_w2, buff_w2-buff_w, ans)
        ans = min(ans, buff_w2 - buff_w)




    # if menseki % 2 == 0:
    #     if menseki/2 <= _a:
    #         ans = min(ans, _a-(menseki//2))
    #     else:
    #         ans = min(ans, (menseki//2)-_a)





print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=10**10
if H>2:
    S=[(H//3),((H-H//3)//2),H-(H//3)-((H-H//3)//2)]
    ans=min(ans,max(S)*W-min(S)*W)
if W>2:
    S=[(W//3),((W-W//3)//2),W-(W//3)-((W-W//3)//2)]
    ans=min(ans,max(S)*H-min(S)*H)
for w in range(1,W):
    S=[w*H,(W-w)*(H//2),(W-w)*(H-H//2)]
    ans=min(ans,max(S)-min(S))
for h in range(1,H):
    S=[h*W,(H-h)*(W//2),(H-h)*(W-W//2)]
    ans=min(ans,max(S)-min(S))
print(ans)

Submission status: Accepted

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

def side(h, W):
    Sa = W * h
    Sb = W * ((H-h)//2)
    Sc = W * ((H-h+1)//2)
    # print (Sa, Sb, Sc)
    return max(Sa, Sb, Sc) - min(Sa, Sb, Sc)

def vertical(h, W):
    Sa = W * h
    Sb = W//2 * (H-h)
    Sc = ((W+1)//2) * (H-h)
    # print (Sa, Sb, Sc)
    return max(Sa, Sb, Sc) - min(Sa, Sb, Sc)


def judge(H, W):
    ans = H * W
    for h in range(0, H):
        # print (side(h, W), vertical(h, W))
        ans = min(ans, side(h, W), vertical(h, W))
        # print (h, W, ans)
    return ans

tmp = judge(H, W)
H, W = W, H
tmp = min(tmp, judge(H, W))
print (tmp)


# print (judge(3, 5))

Submission status: Accepted

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

if H%3 == 0 or W%3 == 0:
    print (0)
elif H == W:
    if H%2 == 0:
        print (H//2)
    else:
        print (H-((2 * H)//6 - H//6))
else:
    if H%2 == 0 and W%2 == 0:
        print (min(H//2, W//2))
    else:
        if H%2 == 0:
            print (min(H//2, H, W))
        elif W%2 == 0:
            print (min(W//2, H, W))
        else:
            print (min(H, W))

Submission status: Accepted

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

if H%3 == 0 or W%3 == 0:
    print (0)
elif H == W:
    if H%2 == 0:
        print (H//2)
    else:
        print (H-((2 * H)//6 - H//6))
elif H%3 == 2 and W%3 == 2:
    if H%2 == 0 and W%2 == 0:
        print (min(H//2, W//2))
    else:
        if H%2 == 0:
            print (H//2)
        elif W%2 == 0:
            print (W//2)
        else:
            print (min(H, W))
elif H%3 == 1 and W%3 == 1:
    if H%2 == 0 and W%2 == 0:
        print (min(H//2, W//2))
    else:
        if H%2 == 0:
            print (H//2)
        elif W%2 == 0:
            print (W//2)
        else:
            print (min(H,W))
else: #この部分に間違い有り
    if H%2 == 0 and W%2 == 0:
        print (min(H//2, W//2))
    else:
        if H%2 == 0:
            print (min(H//2, H, W))
        elif W%2 == 0:
            print (min(W//2, H, W))
        else:
            print (min(H, W))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:print(0)
else:
    l=(h+1)//3
    b=(w+1)//3
    ans=min(w*abs(l-(h-2*l)),h*abs(b-(w-2*b)))
    for x in range(1,w):
        half=h//2
        rest=h-h//2
        sub=max(x*half,x*rest,(w-x)*h)-min(x*half,x*rest,(w-x)*h)
        ans=min(ans,sub)

    for y in range(1,h):
        half=w//2
        rest=w-w//2
        sub=max(y*half,y*rest,(h-y)*w)-min(y*half,y*rest,(h-y)*w)
        ans=min(ans,sub)
    print(ans)

Submission status: Accepted

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

def calc2(H,W):
    if H>W:
        H,W=W,H
        
    if H%2==1 and W%2==1:
        return [H*(W//2),H*W-H*(W//2)]
    else:
        return [H*W//2]
    

def calc(H,H2,W):
    SQ=[H2*W]
    SQ+=calc2(H-H2,W)
    return max(SQ)-min(SQ)

    
ANS=float("inf")
ANS=min(ANS,calc(H,H//3,W))
ANS=min(ANS,calc(H,H//3+1,W))
ANS=min(ANS,calc(W,W//3,H))
ANS=min(ANS,calc(W,W//3+1,H))

print(ANS)

Submission status: Accepted

Solution code:
## 題意を愚直に実装した

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

## 分け方は4通りしかない
## 全て縦に分割する/全て横に分割する/縦1横2に分割する/縦2横1に分割する

solver = []

## どちらかの辺が3で割り切れる場合は、平等に分配できる
if H % 3 == 0 or W % 3 == 0:
  print(0)
  exit()

## 全て縦に分割する
solver.append(H)
## 全て横に分割する
solver.append(W)

## 縦1横2に分割する
for height in [(H-1)//2, H//2, (H+1)//2]: ## 思考停止脳筋候補全列挙
  for length in [(W-1)//3, W//3, (W+1)//3]:
    area1 = H * length
    area2 = height * (W - length)
    area3 = (H - height) * (W - length)
    solver.append(max(area1,area2,area3) - min(area1,area2,area3))
    
## 縦2横1に分割する
for height in [(H-1)//3, H//3, (H+1)//3]:
  for length in [(W-1)//2, W//2, (W+1)//2]:
    area1 = height * W 
    area2 = (H - height) * length
    area3 = (H - height) * (W - length)
    solver.append(max(area1,area2,area3) - min(area1,area2,area3))
    
print(min(solver))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=min((0--h//3-h//3)*w,(0--w//3-w//3)*h)
for i in range(1,h):
  a,b,c=sorted((i*w,-~w//2*(h-i),w//2*(h-i)))
  m=min(m,c-a)
for i in range(1,w):
  a,b,c=sorted((i*h,-~h//2*(w-i),h//2*(w-i)))
  m=min(m,c-a)
print(m)