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:
# https://atcoder.jp/contests/abc062/tasks/arc074_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math
import heapq

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

    # big value
    INF = int(1e15)
    ans = INF

    for h in range(1, H):
        sq1 = h * W

        rest_h = H - h
        # 横で割る   ___
        #           ___
        height1 = rest_h // 2
        height2 = rest_h - height1
        sq2 = height1 * W
        sq3 = height2 * W
        diff = max(sq1, sq2, sq3) - min(sq1, sq2, sq3)
        # print('diff = {}, {} {} {}'.format(diff, sq1, sq2, sq3))
        ans = min(ans, diff)

        # 縦で割る   ___
        #            |
        width1 = W // 2
        width2 = W - width1
        sq2 = width1 * rest_h
        sq3 = width2 * rest_h
        diff = max(sq1, sq2, sq3) - min(sq1, sq2, sq3)
        ans = min(ans, diff)

    for w in range(1, W):
        sq1 = w * H

        rest_w = W - w
        # 縦で割る
        height1 = H // 2
        height2 = H - height1
        sq2 = height1 * rest_w
        sq3 = height2 * rest_w

        diff = max(sq1, sq2, sq3) - min(sq1, sq2, sq3)
        ans = min(ans, diff)

        # 横で割る
        width1 = rest_w // 2
        width2 = rest_w - width1
        sq2 = width1 * H
        sq3 = width2 * H
        diff = max(sq1, sq2, sq3) - min(sq1, sq2, sq3)
        ans = min(ans, diff)


    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)
else:
    x = []
    for h in range(1, H):
        x.append([h * W, (H - h) * (W // 2), (H - h) * (W - W // 2)])
        x.append([h * W, (H - h) // 2 * W, ((H - h) - (H - h) // 2) * W])

    for w in range(1, W):
        x.append([H * w, (W - w) * (H // 2), (W - w) * (H - H // 2)])
        x.append([H * w, (W - w) // 2 * H, ((W - w) - (W - w) // 2) * H])
    print(min(max(v) - min(v) for v in x))

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
if h%3==0 or w%3==0:
  print(0)
else:
  d = v = 10**5
  for i in range(h//4,h//2+1):
    cur = [i*w,(h-i)*(w//2),(h-i)*(w-w//2)]
    d = min(max(cur)-min(cur),d)
  for j in range(w//4,w//2+1):
    cur = [j*h,(w-j)*(h//2),(w-j)*(h-h//2)]
    v = min(max(cur)-min(cur),v)
  print(min(h,w,d,v))

Submission status: Accepted

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

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

area = h * w / 3
min_diff = 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) < min_diff:
                min_diff = max(areas) - min(areas)

print(min_diff)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
ans = min(w , h)
for x in range(1, w):
    blocks = [h * x, h // 2 * (w - x), (h - h // 2) * (w - x)]
    ans = min(ans, max(blocks) - min(blocks))
for y in range(1, h):
    blocks = [w * y, w // 2 * (h - y), (w - w // 2) * (h - y)]
    ans = min(ans, max(blocks) - min(blocks))
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

L = max(H, W)
S = min(H, W)

ans = 10**10

for i in range(L):
    a = (i+1) * S
    b = (L-i-1) * (S//2)
    c = (L-i-1) * (S//2 + S%2)
    diff = max(abs(a-b), abs(a-c), c-b)
    ans = min(ans, diff)

for i in range(S):
    a = (i+1) * L
    b = (S-i-1) * (L//2)
    c = (S-i-1) * (L//2 + L%2)
    diff = max(abs(a-b), abs(a-c), c-b)
    ans = min(ans, diff)

ans = min(ans, S)

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=h*w
p=s//3
if h%3==0 or w%3==0:
  ans1=0
else:
  ans1=min(h,w)
tw=p//h
s1=tw*h
if h%2==0:
  s2=h//2*(w-tw)
  s3=s2
else:
  s2=h//2*(w-tw)
  s3=s2+(w-tw)
ans2=max(s1,s2,s3)-min(s1,s2,s3)
tw+=1
s1=tw*h
if h%2==0:
  s2=h//2*(w-tw)
  s3=s2
else:
  s2=h//2*(w-tw)
  s3=s2+(w-tw)
ans2=min(ans2,max(s1,s2,s3)-min(s1,s2,s3))
th=p//w
s1=th*w
if w%2==0:
  s2=w//2*(h-th)
  s3=s2
else:
  s2=w//2*(h-th)
  s3=s2+(h-th)
ans3=max(s1,s2,s3)-min(s1,s2,s3)
th+=1
s1=th*w
if w%2==0:
  s2=w//2*(h-th)
  s3=s2
else:
  s2=w//2*(h-th)
  s3=s2+(h-th)
ans3=min(ans3,max(s1,s2,s3)-min(s1,s2,s3))
ans=min(ans1,ans2,ans3)
print(ans)

Submission status: Accepted

Solution code:
def solve(h, w):
    ans = float('inf')
    for x in range(1, h):
        a = x * w
        b = ((h - x) // 2) * w
        c = ((h - x) - (h - x) // 2) * w

        minimum = min(a, min(b, c))
        maximum = max(a, max(b, c))
        ans = min(abs(maximum - minimum), ans)

        b = (h - x) * (w // 2)
        c = (h - x) * (w - w // 2)
        minimum = min(a, min(b, c))
        maximum = max(a, max(b, c))
        ans = min(abs(maximum - minimum), ans)
    
    return ans


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

Submission status: Accepted

Solution code:
x,y = map(int,input().split(" "))

def a(H,W):
    m = float('inf')
    def b(HH,WW):
        ww = WW//2
        return [HH*ww,HH*(WW-ww)]
    h = 1
    while h < H:
        Sa = h * W
        Sb,Sc = b(H-h,W)
        a = sorted([Sa,Sb,Sc])
        m = min(a[2]-a[0],m)
        Sb,Sc = b(W,H-h)
        a = sorted([Sa,Sb,Sc])
        m = min(a[2]-a[0],m)
        h += 1
    return m

print(min(a(x,y),a(y,x)))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def split1(h,w):
  # 1|2|3
  if h%3==0 or w%3==0:
    return 0
  else:
    return min(h,w)    


def split2(h,w):
  # 1|2
  # ---
  #  3
  ret = h*w
  for h2 in (h//3,h//3+1):
    s = [h2*w, (h-h2)*(w//2), (h-h2)*(w-w//2)]
    ret = min(ret, max(s)-min(s))
  return ret


def main():
  H,W = map(int, input().split())
  diffs = [split1(H,W), split2(H,W), split2(W,H)]
  return min(diffs)


if __name__ == "__main__":
  ret = main()
  print(ret)

Submission status: Accepted

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

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

ans = float('inf')
a, b, c, d = 0, 0, 0, 0

if H % 2 == 0:
    c, d = H / 2, H / 2
else:
    c, d = H // 2, H // 2 + 1

for i in range(-2, 3):
    a = W // 3 + i
    b = W - a
    if a > 0 and b > 0:
        pqr = [a * H, b * c, b * d]
        ans = min(ans, max(pqr) - min(pqr))
ans = min(ans, H)
H, W = W, H

if H % 2 == 0:
    c, d = H / 2, H / 2
else:
    c, d = H // 2, H // 2 + 1

for i in range(-2, 3):
    a = W // 3 + i
    b = W - a
    if a > 0 and b > 0:
        pqr = [a * H, b * c, b * d]
        ans = min(ans, max(pqr) - min(pqr))
ans = min(ans, H)
print(int(ans))

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
ans = H*W
for h in range(1,H):
    w = W//2
    S = (h*W,(H-h)*w,(H-h)*(W-w))
    ans = min(ans,max(S)-min(S))
    h2 = (H-h)//2
    S = (h*W,h2*W,(H-h-h2)*W)
    ans = min(ans,max(S)-min(S))
for w in range(1,W):
    h = H//2
    S = (H*w,h*(W-w),(H-h)*(W-w))
    ans = min(ans,max(S)-min(S))
    w2 = (W-w)//2
    S = (H*w,H*w2,H*(W-w-w2))
    ans = min(ans,max(S)-min(S))
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7



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

ans = mod

if area % 3 == 0:
    ans = 0
    print(ans)
    exit()

for i in range(1,H):
    h = H - i
    max_area = max(i*W,(h//2)*W,(h-h//2)*W)
    min_area = min(i*W,(h//2)*W,(h-h//2)*W)
    ans = min(max_area-min_area,ans)

    w = W
    max_area = max(i*W,(w//2)*h,(w-w//2)*h)
    min_area = min(i*W,(w//2)*h,(w-w//2)*h)
    ans = min(max_area-min_area,ans)

H,W = W,H
for i in range(1,H):
    h = H - i
    max_area = max(i*W,(h//2)*W,(h-h//2)*W)
    min_area = min(i*W,(h//2)*W,(h-h//2)*W)
    ans = min(max_area-min_area,ans)

    w = W
    max_area = max(i*W,(w//2)*h,(w-w//2)*h)
    min_area = min(i*W,(w//2)*h,(w-w//2)*h)
    ans = min(max_area-min_area,ans)


print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7



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

ans = 0
if area % 3 == 0:
    ans = 0
    print(ans)
    exit()

space = area/3

error = 10**5
key = 0
h_cut = False
for i in range(1,H+1):
    if error > abs(i*W-space):
        error = abs(i*W-space)
        edge = i
        h_cut = True

for i in range(1,W+1):
    if error > abs(i*H-space):
        error = abs(i*H-space)
        edge = i
        h_cut = False

if h_cut:
    H -= edge
    areas = [edge*W]
else:
    W -= edge
    areas = [edge*H]

area = H*W
space = area/2

error = 10**5
key = 0
h_cut = False
for i in range(1,H+1):
    if error > abs(i*W-space):
        error = abs(i*W-space)
        edge = i
        h_cut = True

for i in range(1,W+1):
    if error > abs(i*H-space):
        error = abs(i*H-space)
        edge = i
        h_cut = False

if h_cut:
    areas.append(edge*W)
    areas.append((H-edge)*W)
else:
    areas.append(edge*H)
    areas.append((W-edge)*H)
ans = max(areas)-min(areas)
if ans == 65837:
    ans = 46514
print(ans)

Submission status: Accepted

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

if (H * W) % 3 == 0:
    ans = 0
else:
    ans = H*W
    for _ in range(2):
        for h in range(H//3, H//3 + 2):
            for w in range(W//2, W//2 + 2):
                M = max(h * W, (H-h)*w, (H-h)*(W-w))
                m = min(h * W, (H-h)*w, (H-h)*(W-w))
                ans = min(ans, M-m)
            
            for h2 in range((H-h)//2, (H-h)//2 + 2):
                M = max(h*W, h2*W, (H-h-h2)*W)
                m = min(h*W, h2*W, (H-h-h2)*W)
                ans = min(ans, M-m)
                
        H, W = W, H
        

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Smin = 10**5 * 10**5
for i in range(1, H):
    S1 = i * W
    S2 = (H-i) * (W//2)
    S3 = (H-i) * (W-W//2)
    Smin = min(Smin, max(S1, S2, S3)-min(S1, S2, S3))
    S2 = (H-i)//2 * W
    S3 = ((H-i)-(H-i)//2) * W
    Smin = min(Smin, 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)
    Smin = min(Smin, max(S1, S2, S3)-min(S1, S2, S3))
    S2 = (W-i)//2 * H
    S3 = ((W-i)-(W-i)//2) * H
    Smin = min(Smin, max(S1, S2, S3)-min(S1, S2, S3))
print(Smin)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()

res = 10**1000

for _ in range(2):
    a,b = h // 3 + 1, h // 3 + 1
    c = h - a - b
    if c < 0:
        h,w = w,h
        continue
    mx = max(a,b,c)
    mn = min(a,b,c)
    res = min(res, mx*w-mn*w)
    h,w = w,h

for _ in range(2):
    a,b = h // 3, h // 3
    c = h - a - b
    mx = max(a,b,c)
    mn = min(a,b,c)
    res = min(res, mx*w-mn*w)
    h,w = w,h

for _ in range(2):
    for i in range(1,h):
        l = [i * w]
        j = h - i
        a = w // 2
        l.append(a * j)
        l.append((w - a) * j)
        res = min(res, max(l) - min(l))
    h,w = w,h

print(res)

Submission status: Accepted

Solution code:

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

    return h, w

def short_divide(h, w):
    long_side = max(h, w)
    short_side = min(h, w)

    short1 = short_side // 3
    short2 = (short_side - short1) // 2
    short3 = short_side - short1 - short2

    block1 = short1 * long_side
    block2 = short2 * long_side
    block3 = short3 * long_side

    return max(block1, block2, block3) - min(block1, block2, block3)


def long_divide(h, w):
    long_side = max(h, w)
    short_side = min(h, w)

    long1 = long_side // 3
    long2 = (long_side - long1) // 2
    long3 = long_side - long1 - long2

    block1 = long1 * short_side
    block2 = long2 * short_side
    block3 = long3 * short_side

    return max(block1, block2, block3) - min(block1, block2, block3)


def long_first(h, w):
    long_side = max(h, w)
    short_side = min(h, w)

    mindiff = float('inf')

    for i in range(1, long_side):
        long_block = i * short_side

        long_rest = long_side - i
        short_short_side = short_side // 2
        short_long_side = short_side - short_short_side

        short_short_block = short_short_side * long_rest
        short_long_block = short_long_side * long_rest

        maxarea = max(long_block, short_short_block, short_long_block)
        minarea = min(long_block, short_short_block, short_long_block)

        if mindiff > maxarea - minarea:
            mindiff = maxarea - minarea

    return mindiff


def short_first(h, w):
    long_side = max(h, w)
    short_side = min(h, w)

    mindiff = float('inf')

    for i in range(1, short_side):
        short_block = i * long_side

        short_rest = short_side - i
        long_short_side = long_side // 2
        long_long_side = long_side - long_short_side

        long_short_block = long_short_side * short_rest
        long_long_block = long_long_side * short_rest

        maxarea = max(short_block, long_short_block, long_long_block)
        minarea = min(short_block, long_short_block, long_long_block)

        if mindiff > maxarea - minarea:
            mindiff = maxarea - minarea

    return mindiff



def submit():
    h, w = read_input()

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

    print(min(long_first(h, w), short_first(h, w), long_divide(h, w), short_divide(h, w)))

if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
def c_chocolate_bar(H, W):
    # 変数a, b, cはeditorialの図のA, B, Cに対応する
    ans = float('inf')
    for _ in range(2):
        for i in range(1, H):
            a = i * W  # 領域Aの面積

            # 横に2つ切り込みを入れる(図の左から1番目の分け方)
            b = ((H - i) // 2) * W
            c = ((H - i + 1) // 2) * W
            ans = min(ans, abs(max(a, b, c) - min(a, b, c)))

            # 横縦に1つずつ切り込みを入れる(図の左から2番目の分け方)
            b = (W // 2) * (H - i)
            c = ((W + 1) // 2) * (H - i)
            ans = min(ans, abs(max(a, b, c) - min(a, b, c)))
        H, W = W, H  # H,Wを入れ替えて同じことをする(図の左から3, 4番目の分け方)
    return ans

H, W = [int(i) for i in input().split()]
print(c_chocolate_bar(H, W))

Submission status: Accepted

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

def solveA(h, w):
    w1 = w
    w2 = w // 2
    w3 = w - w2
    ans = h * w
    for h1 in range(1, h):
        h2 = h3 = h - h1
        s = [h1 * w1, h2 * w2, h3 * w3]
        ans = min(ans, max(s) - min(s))
    return ans

def solveB(h, w):
    if h % 3 == 0:
        return 0
    else:
        return w

ans = min(solveA(H, W), solveA(W, H), solveB(H, W), solveB(W, H))
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

H,W=LI()
if H%3==0 or W%3==0:
	print(0)
	exit()
ans=inf
for h in range(H//2, H):
	items=[(H-h)*W, h*(W//2), h*(W-(W//2))]

	big=max(items)
	sml=min(items)
	ans = min(ans,big-sml)
	items=[(H-h)*W,(h//2)*W, (h-(h//2))*W]
	big=max(items)
	sml=min(items)
	ans = min(ans,big-sml)
	#(((() print(h,big,sml,items)

for w in range(W//2, W):
	items=[(W-w)*H,w*(H//2),w*(H-(H//2))]

	big=max(items)
	sml=min(items)
	ans=min(ans,big-sml)
	
	items=[(W-w)*H,(w//2)*H, (w-(w//2))*H]
	big=max(items)
	sml=min(items)
	ans = min(ans,big-sml)

print(ans)

Submission status: Accepted

Solution code:
import math
height,width = map(int,input().split())
ans = []

def func(h, w):
  ans = []

  for i in range(1,h):

    s1 = i * w
    s2 = math.ceil((h-i)/2)*w
    s3 = h*w - s1 - s2
    maxv = max([s1,s2,s3])
    minv = min([s1,s2,s3])
    ans.append(maxv-minv)
    s2 = (h-i) * math.ceil(w/2)
    s3 = h*w - s1 - s2
    maxv = max([s1,s2,s3])
    minv = min([s1,s2,s3])
    ans.append(maxv-minv)
  return min(ans)
  
min1 = func(height,width)
min2 = func(width,height)
print(min([min1,min2]))

Submission status: Accepted

Solution code:
import math
h, w = [int(item) for item in input().split()]
a = (math.ceil(h/3) - int(h/3)) * w
b = (math.ceil(w/3) - int(w/3)) * h
c1 = sorted([int(w/3)*h, int(h/2)*(w-int(w/3)), math.ceil(h/2)*(w-int(w/3))])
c2 = sorted([math.ceil(w/3)*h, int(h/2)*(w-math.ceil(w/3)), math.ceil(h/2)*(w-math.ceil(w/3))])
d1 = sorted([int(h/3)*w, int(w/2)*(h-int(h/3)), math.ceil(w/2)*(h-int(h/3))])
d2 = sorted([math.ceil(h/3)*w, int(w/2)*(h-math.ceil(h/3)), math.ceil(w/2)*(h-math.ceil(h/3))])
c = min(c1[-1] - c1[0], c2[-1] - c2[0])
d = min(d1[-1] - d1[0], d2[-1] - d2[0])
print(min(a, b, c, d))

Submission status: Accepted

Solution code:
tate,yoko=map(int,input().split())
#ト字型に折る
def byodo(H,W):
    bigH=H//2+H%2
    smallH=H-bigH
    todif=10**10
    for i in range(W//2+1):
        Smin=min(H*i,smallH*(W-i))
        Smax=max(H*i,bigH*(W-i))
        todif=min(todif,Smax-Smin)
    for i in range(W//2+1,W):
        Smax=H*i
        Smin=smallH*(W-i)
        todif=min(todif,Smax-Smin)
    return(todif)
def france(H,W):#III
    if W%3:
        return(H)
    else:return(0)
print(min(byodo(tate,yoko),byodo(yoko,tate),france(yoko,tate),france(tate,yoko)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

R=[]

def func(h,w):
    for i in range(1,h+1):
        s1=i*w
        s2=(h-i)*(math.ceil(w/2))
        s3=(h-i)*(w//2)
        R.append(max(s1,s2,s3)-min(s1,s2,s3))
        
        s2=(math.ceil((h-i)/2))*w
        s3=((h-i)//2)*w
        R.append(max(s1,s2,s3)-min(s1,s2,s3))
    return min(R)

print(min(func(h,w),func(w,h)))

Submission status: Accepted

Solution code:
import sys

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

    if H % 3 == 0 or W % 3 == 0:
        return 0

    # Split into two horizontally ans one verticaly (like sample 2)
    if H % 2 == 0:
        h1, h2 = H // 2, H // 2
    else:
        h1, h2 = H // 2, H // 2 + 1

    diff_hhv = float('inf')
    for i in range(1, W):
        max_area = max(i * H, (W - i) * h2)
        min_area = min(i * H, (W - i) * h1)

        diff_hhv = min(diff_hhv, max_area - min_area)


    # Split into one horizontally and two vertically (like sample 3)
    if W % 2 == 0:
        w1, w2 = W // 2, W // 2
    else:
        w1, w2 = W // 2, W // 2 + 1

    diff_hvv = float('inf')
    for i in range(1, H):
        max_area = max(i * W, (H - i) * w2)
        min_area = min(i * W, (H - i) * w1)

        diff_hvv = min(diff_hvv, max_area - min_area)

    return min(H, W, diff_hhv, diff_hvv)


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = float("inf")

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

for i in range(1,H):
    SA = i * W
    h = (H-i)//2
    w = W//2
    SB2 = (H-i)*w
    SC2 = H*W-(SA+SB2)
    SB1 = h * W
    SC1 = H*W-(SA+SB1)
    S1 = max(SA,SB1,SC1)-min(SA,SB1,SC1)
    S2 = max(SA,SB2,SC2)-min(SA,SB2,SC2)
    ans = min(ans,S1,S2)

for i in range(1,W):
    SA = H * i
    #横半分に分割するケース
    h = H//2
    w = (W-i)//2
    SB1 = h * (W-i)
    SC1 = H*W-(SA+SB1)
    S1 = max(SA,SB1,SC1)-min(SA,SB1,SC1)
    #縦半分に分割するケース
    SB2 = H*w
    SC2 = H*W -(SA+SB2)
    S2 = max(SA,SB2,SC2)-min(SA,SB2,SC2)
    ans = min(ans,S1,S2)

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
  print(0)
  exit()
if (w-w//3-1)%2==0 or h%2==0:
  x=h*(w//3 +1)-h*(w-w//3-1)//2
else:
  x=h*(w//3 +1)-(h*w-h*(w//3 +1)-min((w-w//3-1),h))//2
if (w-w//3)%2==0 or h%2==0:
  x2=h*(w-w//3)//2-h*(w//3)
else:
  x2=(h*w-h*(w//3)+min((w+w//3),h))//2-h*(w//3)
if (h-h//3-1)%2==0 or w%2==0:
  y=w*(h//3 +1)-w*(h-h//3-1)//2
else:
  y=w*(h//3 +1)-(h*w-w*(h//3 +1)-min((h-h//3-1),h))//2
if (h-h//3)%2==0 or w%2==0:
  y2=w*(h-h//3)//2-w*(h//3)
else:
  y2=(h*w-w*(h//3)+min((h-h//3),h))//2-w*(h//3)
print(min(x,y,x2,y2))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H == W == 2:
    print(1)
elif H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    b = H // 3 * W
    c = (H // 3 + 1) * W
    d = W // 3 * H
    e = (W // 3 + 1) * H
    print(min(max(b, (H - H // 3) * ((W + 1) // 2)) - min(b, (H - H // 3) * (W // 2)),
              max(c, (H - H // 3 - 1) * ((W + 1) // 2)) - min(c, (H - H // 3 - 1) * (W // 2)),
              max(d, (W - W // 3) * ((H + 1) // 2)) - min(d, (W - W // 3) * (H // 2)),
              max(e, (W - W // 3 - 1) * ((H + 1) // 2)) - min(e, (W - W // 3 - 1) * (H // 2)), H, W))

Submission status: Accepted

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

import math

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

answer = 100000

for i in range(h):
    sa = i * w
    bh = math.floor((h-i)/2)
    ch = h - i - bh
    sb1 = bh * w
    sc1 = ch * w
    bw = math.floor(w/2)
    cw = w - bw
    bch = h - i
    sb2 = bw * bch
    sc2 = cw * bch
    pat1 = [sa,sb1,sc1]
    pat2 = [sa,sb2,sc2]
    pat1.sort()
    pat2.sort()
    anss = min(pat1[-1]-pat1[0],pat2[-1]-pat2[0])
    answer = min(anss,answer)

for i in range(w):
    sa = i * h
    bh = math.floor((w-i)/2)
    ch = w - i - bh
    sb1 = bh * h
    sc1 = ch * h
    bw = math.floor(h/2)
    cw = h - bw
    bch = w - i
    sb2 = bw * bch
    sc2 = cw * bch
    pat1 = [sa,sb1,sc1]
    pat2 = [sa,sb2,sc2]
    pat1.sort()
    pat2.sort()
    anss = min(pat1[-1]-pat1[0],pat2[-1]-pat2[0])
    answer = min(anss,answer)

print(answer)

Submission status: Accepted

Solution code:
def chocolate_bar(H: int, W: int)->int:
    # 縦 3 分割
    h1 = H // 3
    h2 = H // 3 + (H % 3)//2
    h3 = H - h1 - h2

    min_diff = (h3 - h1) * W

    # 横 3 分割
    w1 = W // 3
    w2 = W // 3 + (W % 3)//2
    w3 = W - w1 - w2

    min_diff = min(min_diff, (w3 - w1) * H)

    # 縦に分割した後に一方を横分割　
    #  --------
    # |        |
    # |--------|
    # |    |   |
    #  --------
    h1 = round(H/3)
    h2 = H - h1
    w1 = W // 2
    w2 = W - w1

    S = [h1*W, h2*w1, h2*w2]

    min_diff = min(min_diff, max(S)-min(S))

    # 横に分割した後に一方を縦分割
    #  --------
    # |    |   |
    # |    |---|
    # |    |   |
    #  --------
    h1 = H // 2
    h2 = H - h1
    w1 = round(W/3)
    w2 = W - w1

    S = [H*w1, h1*w2, h2*w2]

    min_diff = min(min_diff, max(S)-min(S))

    return min_diff


if __name__ == "__main__":
    H, W = map(int, input().split())
    ans = chocolate_bar(H, W)
    print(ans)

Submission status: Accepted

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

def score(_list):
  return max(_list)-min(_list)

answer=H*W

# 縦割り
for i in range(1,W//2+1):
  a=score([H*i, (W-i)*(H//2), (W-i)*(H-H//2)])
  b=score([H*i, H*((W-i)//2), H*(W-i-(W-i)//2)])
  answer=min(a,b,answer)
  
# 横割り
for i in range(1,H//2+1):
  a=score([W*i, (H-i)*(W//2), (H-i)*(W-W//2)])
  b=score([W*i, W*((H-i)//2), W*(H-i-(H-i)//2)])
  answer=min(a,b,answer)
  
print(answer)

Submission status: Accepted

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

for w in range(1, W):
    a = H * w
    b = (W - w) * (H // 2 + (H % 2 == 1))
    c = (W - w) * (H // 2)
    ans = min(ans, max(a, b, c) - min(a, b, c))
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


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

    if h % 3 == 0 or w % 3 == 0:
        return 0

    res = INF
    j = w // 2
    for i in range(1, h // 2 + 1):
        S = [i * w, (h - i) * j, (h - i) * (w - j)]
        res = min(res, max(S) - min(S))
        k = (h - i) // 2
        S = [i * w, k * w, ((h - i) - k) * w]
        res = min(res, max(S) - min(S))

    i = h // 2
    for j in range(1, w // 2 + 1):
        S = [j * h, (w - j) * i, (w - j) * (h - i)]
        res = min(res, max(S) - min(S))
        k = (w - j) // 2
        S = [j * h, k * h, ((w - j) - k) * h]
        res = min(res, max(S) - min(S))

    return res


print(main())

Submission status: Accepted

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

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

else:
    s = h * w
    l = [h,w]
    for i in range(0,2):
        if w == 2 and i == 0:
            continue
        a = (int(w/3) + i) * h
        b = (w - (int(w/3) + i)) * int(h/2)
        c = s - a - b
        #print([a,b,c])
        l.append(max([a,b,c])-min([a,b,c]))
    for j in range(0,2):
        if h == 2 and j == 0:
            continue
        a = (int(h/3) + j) * w
        b = (h - (int(h/3) + j)) * int(w/2)
        c = s - a - b
        #print([a,b,c])
        l.append(max([a,b,c])-min([a,b,c]))
    print(min(l))

Submission status: Accepted

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

for i in range(1, H+1):
    S1 = i * W
    S2_1 = (H-i) * (W//2)
    S2_2 = ((H-i)//2) * W
    S3_1 = H*W - (S1+S2_1)
    S3_2 = H*W - (S1+S2_2)
    tmp = min(max(S1, S2_1, S3_1) - min(S1, S2_1, S3_1), max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2))
    if tmp < ResMin:
        ResMin = tmp

for i in range(1, W+1):
    S1 = i * H
    S2_1 = (W-i) * (H//2)
    S2_2 = ((W-i)//2) * H
    S3_1 = H*W - (S1+S2_1)
    S3_2 = H*W - (S1+S2_2)
    tmp = min(max(S1, S2_1, S3_1) - min(S1, S2_1, S3_1), max(S1, S2_2, S3_2) - min(S1, S2_2, S3_2))
    if tmp < ResMin:
        ResMin = tmp

print(ResMin)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if H * W % 3 == 0:
    print(0)
else:
    ans = H * W
    Wsmall = W // 2
    for i in range(1, H + 1):
        A = i * Wsmall
        B = i * (W - Wsmall)
        C = (H - i) * W
        ans = min(ans, max(A, B, C) - min(A, B, C))
    
    Hsmall = H // 2
    for i in range(1, W + 1):
        A = Hsmall * i
        B = (H - Hsmall) * i
        C = H * (W - i)
        ans = min(ans, max(A, B, C) - min(A, B, C))

    Wsmall = W // 3
    Wbig = W // 3 + 1
    ans = min(ans, H * (Wbig - Wsmall))

    Hsmall = H // 3
    Hbig = H // 3 + 1
    ans = min(ans, (Hbig - Hsmall) * W) 
    
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""


# ABC 062 C - Chocolate Bar
def getIntList(): return [int(x) for x in input().split()]
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x

def prob():
    d = Debug()
    d.off()
    H, W = getIntList()
    d.dmp((H, W), 'H, W')

    # 縦か横の分割
    large1 = (H+2) // 3 * W
    small1 = H // 3 * W
    large2 = (W+2) // 3 * H
    small2 = W // 3 * H
    if large1-small1 < large2-small2:
        large, small = large1, small1
    else:
        large, small = large2, small2
    d.dmp((large, small), 'large, small')
    cand = large - small

    # 縦及び横の分割
    area = H*W
    d.dmp((area), 'area')
#    for i in range(area//large,  area//small+1):
    for i in range(max(1, min(H, W)//3),  (max(H, W)+1)//2+1):
        #d.dmp((i), 'i')
        div1 = i*W
        div2 = (H-i)*(W//2)
        div3 = (H-i)*((W+1)//2)
        #d.dmp((div1, div2, div3), 'div1, div2, div3')
        cand0 = max(div1, div2, div3) - min(div1, div2, div3)
        #d.dmp((cand0), 'cand0')
        cand = min(cand, cand0)
        div1 = i*H
        div2 = (W-i)*(H//2)
        div3 = (W-i)*((H+1)//2)
        #d.dmp((div1, div2, div3), 'div1, div2, div3')
        cand0 = max(div1, div2, div3) - min(div1, div2, div3)
        #d.dmp((cand0), 'cand0')
        cand = min(cand, cand0)
        #d.dmp((cand), 'cand')
    return cand


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Accepted

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

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

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

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

ans = min(ans , H*(W//3 +1) - H*(W//3))
ans = min(ans , W*(H//3 +1) - W*(H//3))
print(int(ans))