Problem:


Score : 400 points

Problem Statement

There is a bar of chocolate with a height of H blocks and a width of W blocks.
Snuke is dividing this bar into exactly three pieces.
He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.

Snuke is trying to divide the bar as evenly as possible.
More specifically, he is trying to minimize S_{max} - S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece.
Find the minimum possible value of S_{max} - S_{min}.

Constraints

2 ≤ H, W ≤ 10^5

Input

Input is given from Standard Input in the following format:

H W

Output

Print the minimum possible value of S_{max} - S_{min}.

Sample Input 1

3 5

Sample Output 1

0

In the division below, S_{max} - S_{min} = 5 - 5 = 0.

Sample Input 2

4 5

Sample Output 2

2

In the division below, S_{max} - S_{min} = 8 - 6 = 2.

Sample Input 3

5 5

Sample Output 3

4

In the division below, S_{max} - S_{min} = 10 - 6 = 4.

Sample Input 4

100000 2

Sample Output 4

1

Sample Input 5

100000 100000

Sample Output 5

50000



Sample input:
3 5


Sample output:
0

Submission status: Accepted

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

ans = 10 ** 10
for i in range(h):
    x = (i + 1) * w
    mid = (h - i - 1) // 2
    y = mid * w
    z = (h - i - 1 - mid) * w
    ans = min(ans, max(x, y, z) - min(x, y, z))

    mid = w // 2
    y = (h - i - 1) * mid
    z = (h - i - 1) * (w - mid)
    ans = min(ans, max(x, y, z) - min(x, y, z))

for j in range(w):
    x = (j + 1) * h
    mid = (w - j - 1) // 2
    y = mid * h
    z = (w - j - 1 - mid) * h
    ans = min(ans, max(x, y, z) - min(x, y, z))

    mid = h // 2
    y = (w - j - 1) * mid
    z = (w - j - 1) * (h - mid)
    ans = min(ans, max(x, y, z) - min(x, y, z))

print(ans)

Submission status: Accepted

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

def menseki(h,w):
    global ans
    for i in range(1,h):
        # 縦1横2
        haba = w//2
        ans = min(ans,max(i*w,haba*(h-i),(w-haba)*(h-i))-min(i*w,haba*(h-i),(w-haba)*(h-i)))
        # 縦3分割
        if i == h-1:
            continue
        tate = (h-i)//2
        ans = min(ans,max(w*i,tate*w,(h-i-tate)*w)-min(w*i,tate*w,(h-i-tate)*w))

menseki(h,w)
menseki(w,h)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist():
    return list(map(int,input().split()))
######################################################################################################

H,W=inputintlist()
ans=inf
for a in range(1,H):
    A=a*W
    #並行に分割
    B=((H-a)//2)*W
    C=H*W-A-B
    ans=min(ans,max([A,B,C])-min([A,B,C]))
    
    #垂直に分割
    B=(W//2)*(H-a)
    C=H*W-A-B
    ans=min(ans,max([A,B,C])-min([A,B,C]))
    
H,W=W,H
for a in range(1,H):
    A=a*W
    #並行に分割
    B=((H-a)//2)*W
    C=H*W-A-B
    ans=min(ans,max([A,B,C])-min([A,B,C]))
    
    #垂直に分割
    B=(W//2)*(H-a)
    C=H*W-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())
if (H%3) * (W%3) == 0:
  print(0)
  quit()

ans = min(H, W)
w1 = W // 2
w2 = W - w1
S1 = (H - 1) * w1
S2 = (H - 1) * w2
S3 = W
for i in range(H-1):
  diff = max(S1, S2, S3) - min(S1, S2, S3)
  ans = min(ans, diff)
  S1 -= w1; S2 -= w2; S3 += W

h1 = H // 2
h2 = H - h1
S1 = (W - 1) * h1
S2 = (W - 1) * h2
S3 = H
for i in range(W-1):
  diff = max(S1, S2, S3) - min(S1, S2, S3)
  ans = min(ans, diff)
  S1 -= h1; S2 -= h2; S3 += H

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
if (H%3) * (W%3) == 0:
  print(0)
  quit()

ans = H * W
w1 = W // 2
w2 = W - w1
S1 = (H - 1) * w1; T1 = W * ((H-1)//2)
S2 = (H - 1) * w2; T2 = W * (H-1) - T1
S3 = W
h = H - 1
for i in range(H-1):
  diff1 = max(S1, S2, S3) - min(S1, S2, S3)
  diff2 = max(T1, T2, S3) - min(T1, T2, S3)
  ans = min(ans, diff1, diff2)
  S1 -= w1; S2 -= w2; S3 += W
  h -= 1
  T1 = W * (h//2)
  T2 = W*h - T1

h1 = H // 2
h2 = H - h1
S1 = (W - 1) * h1; T1 = H * ((W-1)//2)
S2 = (W - 1) * h2; T2 = H * (W-1) - T1
S3 = H
w = W - 1
for i in range(W-1):
  diff1 = max(S1, S2, S3) - min(S1, S2, S3)
  diff2 = max(T1, T2, S3) - min(T1, T2, S3)
  ans = min(ans, diff1, diff2)
  S1 -= h1; S2 -= h2; S3 += H
  w -= 1
  T1 = H * (w//2)
  T2 = H*w - T1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    ans=INF
    for i in range(1,H):
        S0=W*i
        S1=(H-i)*(W//2)
        S2=(H-i)*(-(-W//2))
        S3=W*((H-i)//2)
        S4=W*(-((i-H)//2))
        ans=min(ans,max(abs(S0-S1),abs(S0-S2)),max(abs(S0-S3),abs(S0-S4)))
    for i in range(1,W):
        S0=H*i
        S1=(W-i)*(H//2)
        S2=(W-i)*(-(-H//2))
        S3=H*((W-i)//2)
        S4=H*(-((i-W)//2))
        ans=min(ans,max(abs(S0-S1),abs(S0-S2)),max(abs(S0-S3),abs(S0-S4)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    H,W = map(int,input().split())
    
    ans = float('inf')
    a = 0
    b = 0
    c = 0

    for h in range(H+1):
        if W % 2 == 0:
            a = h * W // 2
            b = h * W // 2
        else:
            a = h * (W-1) // 2
            b = h * (W+1) // 2
        c = W * (H-h)

        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans, s_max-s_min)

        a = h * W
        if (H-h) % 2 == 0:
            b = (H-h) // 2 * W
            c = (H-h) // 2 * W
        else:
            b = (H-h-1) // 2 * W
            c = (H-h+1) // 2 * W
        
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans, s_max-s_min)

    for w in range(W+1):
        if H % 2 == 0:
            a = w * H // 2
            b = w * H // 2
        else:
            a = w * (H-1) // 2
            b = w * (H+1) // 2
        c = H * (W-w)

        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans, s_max-s_min)

        a = w * H
        if (W-w) % 2 == 0:
            b = (W-w) // 2 * H
            c = (W-w) // 2 * H
        else:
            b = (W-w-1) // 2 * H
            c = (W-w+1) // 2 * H
        
        s_max = max(a,b,c)
        s_min = min(a,b,c)
        ans = min(ans, s_max-s_min)
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def case1(h, w):
    MIN = float('inf')
    for i in range(1, h):
        sa = i * w
        sb = (h - i) * (w//2)
        sc = (h - i) * (w - w//2)
        if max([sa,sb,sc]) - min([sa,sb,sc]) < MIN:
            MIN = max([sa,sb,sc]) - min([sa,sb,sc]) 
    return MIN

def case2(h, w):
    MIN = float('inf')
    for i in range(1, h):
        sa = i * w
        sb = (h - i)//2 * w
        sc = (h - i -(h - i)//2) * w
        if max([sa,sb,sc]) - min([sa,sb,sc]) < MIN:
            MIN = max([sa,sb,sc]) - min([sa,sb,sc]) 
    return MIN
print(min([case1(H,W) , case1(W,H), case2(H,W), case2(W,H)]))

Submission status: Accepted

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

ans = float("inf")
for h, w in zip([H, W], [W, H]):
    # ah の全探索
    for ah in range(1, h):
        # 残りを縦割り
        Sa = ah * w
        bw = (w - 1) // 2 + 1
        Sb = (h - ah) * bw
        Sc = (h - ah) * (w - bw)
        ans = min(ans, (max(Sa, Sb, Sc)-min(Sa, Sb, Sc)))

        # 残りを横割り
        if (h - ah) > 1:
            bh = ((h - ah) - 1) // 2 + 1
            Sb = bh * w
            Sc = (h - ah - bh) * w
            ans = min(ans, (max(Sa, Sb, Sc)-min(Sa, Sb, Sc)))
        
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if not h%3 or not w%3:
  print(0)
else:
  ans = min([h, w])
  for i in range(h):
    sub = max([abs(w*i-w//2*(h-i)), abs(w*i-(w-w//2)*(h-i))])
    if ans > sub:
      ans = sub
  for i in range(w):
    sub = max([abs(h*i-h//2*(w-i)), abs(h*i-(h-h//2)*(w-i))])
    if ans > sub:
      ans = sub
  print(ans)

Submission status: Accepted

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

ans = 1e19
##縦方向の探索
for i in range(1,H):
    tate = W*i##上から横に切る
    ##横に切る
    if i < H-1:
        mini = W*((H-i)//2)##分割したやつ
        ##print(tate,mini,H*W-mini-tate)
        ans = min(ans,max(tate,mini,H*W-mini-tate)-min(tate,mini,H*W-mini-tate))

    ##縦に切る
    mini = (H-i)*(W//2)
    ##print(tate,mini,H*W-mini-tate)
    ans = min(ans,max(tate,mini,H*W-tate-mini)-min(tate,mini,H*W-tate-mini))

##横方向の探索
for i in range(1,W):
    yoko = H*i
    if i < W-1:
        mini = H*((W-i)//2)
        ##print(yoko,mini,H*W-mini-yoko)
        ans = min(ans,max(yoko,mini,H*W-mini-yoko)-min(yoko,mini,H*W-yoko-mini))
    mini = (W-i)*(H//2)
    ##print(yoko,mini,H*W-yoko-mini)
    ans = min(ans,max(yoko,mini,H*W-yoko-mini)-min(yoko,mini,H*W-yoko-mini))

print(ans)

Submission status: Accepted

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

    ans = h * w
    for _ in range(2):
        i = h // 3
        j = w // 2

        x = [(i - 1, h - i + 1), (i, h - i), (i + 1, h - i - 1)]
        y = [(j - 1, w - j + 1), (j, w - j), (j + 1, w - j - 1)]
        for (u, v) in x:
            # case1
            a, b = v // 2, v - v // 2
            s = [w * u, w * a, w * b]
            d = max(s) - min(s)
            ans = min(ans, d)
            for (s, t) in y:
                # case2
                s = [u * w, v * s, v * t]
                d = max(s) - min(s)
                ans = min(ans, d)

        w, h = h, w
    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:
    best = (h*w)/3
    # wから割る方法
    col_num = int(round(best/h))
    remain_w = w - col_num
    h1 = h // 2
    h2 = h - h1
    w1 = remain_w // 2
    w2 = remain_w - w1
    min_area1 = min(remain_w*h1, remain_w*h2, col_num*h) # 垂直
    max_area1 = max(remain_w*h1, remain_w*h2, col_num*h)
    min_area2 = min(w2*h, w1*h, col_num*h) # 平行
    max_area2 = max(w2*h, w1*h, col_num*h)
    num_w1 = max_area1 - min_area1
    num_w2 = max_area2 - min_area2
    # hから割る方法
    row_num = int(round(best/w))
    remain_h = h - row_num
    w1 = w // 2
    w2 = w - w1
    h1 = remain_h // 2
    h2 = remain_h - h1
    min_area1 = min(remain_h*w1, remain_h*w2, row_num*w) # 垂直
    max_area1 = max(remain_h*w1, remain_h*w2, row_num*w)
    min_area2 = min(h2*w, h1*w, row_num*w) # 平行   
    max_area2 = max(h2*w, h1*w, row_num*w)
    num_h1 = max_area1 - min_area1
    num_h2 = max_area2 - min_area2
    print(min(num_h1,num_w1,num_h2,num_w2))

Submission status: Accepted

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

ans = 10 ** 10
for i in range(1, h + 1):
    a = i * w
    b = (h - i) * (w // 2)
    c = ((h - i) * w) - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
for i in range(1, w + 1):
    a = i * h
    b = (w - i) * (h // 2)
    c = ((w - i) * h) - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
for i in range(1, h + 1):
    a = i * w
    b = ((h - i) // 2) * w
    c = ((h - i) * w) - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
for i in range(1, w + 1):
    a = i * h
    b = ((w - i) // 2) * h
    c = ((w - i) * h) - b
    ans = min(ans, max(a, b, c) - min(a, b, c))
print(ans)

Submission status: Accepted

Solution code:
def abc062_c():
    h, w = map(int, input().split())
    # 2 <= h, w のため1の場合は考えない
    # どちらかが3の倍数ならぴったり3分割できる (平行2線)
    if h % 3 == 0 or w % 3 == 0:
        print(0)
        return
    # 平行2線で割るときの差分最小は、短辺1本分
    ans = min(h, w)
    # それ以外は例2例3の割り方 (直交2線)
    for x, y in [(w, h), (h, w)]:
        for i in range(1, x):
            sa = i * y
            sb = (x - i) * (y // 2)
            sc = (x - i) * (y - y // 2)
            diff = max(sa, sb, sc) - min(sa, sb, sc)
            ans = min(diff, ans)
    print(ans)

abc062_c()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
if not h%3 or not w%3:
  print(0)
else:
  ans = min([h, w])
  for i in range(h):
    sub = max([abs(w*i-w//2*(h-i)), abs(w*i-(w-w//2)*(h-i))])
    if ans > sub:
      ans = sub
  for i in range(w):
    sub = max([abs(h*i-h//2*(w-i)), abs(h*i-(h-h//2)*(w-i))])
    if ans > sub:
      ans = sub
  print(ans)

Submission status: Accepted

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

if H%3==0 or W%3==0:
  print(0)
elif H==2 or W==2:
  ans0=min(H,W)
  
  H,W=min(H,W),max(H,W)
  w1=W//3
  w2=W-w1
  s1=2*w1
  s2=w2
  ans1=s2-s1
  
  w1=W//3+1
  w2=W-w1
  s1=2*w1
  s2=w2
  ans2=s1-s2
  print(min(ans0,ans1,ans2))
else:
  ans0=min(H,W)
  
  h1=H//2
  h2=H-h1
  
  w1=W//3
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans1=max(s1,s2,s3)-min(s1,s2,s3)
  
  w1=W//3+1
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans2=max(s1,s2,s3)-min(s1,s2,s3)
  
  H,W=W,H
  h1=H//2
  h2=H-h1
  
  w1=W//3
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans3=max(s1,s2,s3)-min(s1,s2,s3)
  
  w1=W//3+1
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans4=max(s1,s2,s3)-min(s1,s2,s3)
  print(min(ans0,ans1,ans2,ans3,ans4))

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
min_diff = float('inf')
for i in range(1, h + 1):
    sa = i * w
    sb = (h - i) * (w // 2)
    sc = (h - i) * (w - (w // 2))
    min_diff = min(min_diff, max(sa, sb, sc) - min(sa, sb, sc))
    sb = (h - i) // 2 * w
    sc = (h - i - (h - i) // 2) * w
    min_diff = min(min_diff, max(sa, sb, sc) - min(sa, sb, sc))
h, w = w, h
for i in range(1, h + 1):
    sa = i * w
    sb = (h - i) * (w // 2)
    sc = (h - i) * (w - (w // 2))
    min_diff = min(min_diff, max(sa, sb, sc) - min(sa, sb, sc))
    sb = (h - i) // 2 * w
    sc = (h - i - (h - i) // 2) * w
    min_diff = min(min_diff, max(sa, sb, sc) - min(sa, sb, sc))
print(min_diff)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def round(f, r=0):
    return Decimal(str(f)).quantize(Decimal(str(r)), rounding=ROUND_HALF_UP)

def main():
    H, W = map(int, readline().rstrip().split())
    ans = H * W
    if H >= 3:
        y1 = int(round(H/3))
        y2 = (H-y1) // 2
        y3 = H - y1 - y2
        ans = min(ans, max(W*y1, W*y2, W*y3)-min(W*y1, W*y2, W*y3))
    if W >= 3:
        x1 = int(round(W/3))
        x2 = (W-x1) // 2
        x3 = W - x1 - x2
        ans = min(ans, max(x1*H, x2*H, x3*H)-min(x1*H, x2*H, x3*H))
    
    # 縦にスライス + 残りに横にスライス
    x1 = int(round(W/3))
    y1 = H
    x2 = W - x1
    x3 = x2
    y2 = H // 2
    y3 = H - y2
    ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    # 横にスライス + 残りに縦にスライス
    y1 = int(round(H/3))
    x1 = W
    y2 = H - y1
    y3 = y2
    x2 = W // 2
    x3 = W - x2
    ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from math import floor, ceil
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def round(f, r=0):
    return Decimal(str(f)).quantize(Decimal(str(r)), rounding=ROUND_HALF_UP)

def main():
    H, W = map(int, readline().rstrip().split())
    ans = H * W
    if H >= 3:
        y1 = int(round(H/3))
        y2 = (H-y1) // 2
        y3 = H - y1 - y2
        ans = min(ans, max(W*y1, W*y2, W*y3)-min(W*y1, W*y2, W*y3))
    if W >= 3:
        x1 = int(round(W/3))
        x2 = (W-x1) // 2
        x3 = W - x1 - x2
        ans = min(ans, max(x1*H, x2*H, x3*H)-min(x1*H, x2*H, x3*H))
    
    # 縦にスライス + 残りに横にスライス
    x1_cand = [int(round(W/3))]
    y1 = H
    for x1 in x1_cand:
        x2 = W - x1
        x3 = x2
        y2 = H // 2
        y3 = H - y2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    # 横にスライス + 残りに縦にスライス
    y1_cand = [int(round(H/3))]
    x1 = W
    for y1 in y1_cand:
        y2 = H - y1
        y3 = y2
        x2 = W // 2
        x3 = W - x2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from math import floor, ceil
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def round(f, r=0):
    return Decimal(str(f)).quantize(Decimal(str(r)), rounding=ROUND_HALF_UP)

def main():
    H, W = map(int, readline().rstrip().split())
    ans = H * W
    if H >= 3:
        y1 = int(round(H/3))
        y2 = (H-y1) // 2
        y3 = H - y1 - y2
        ans = min(ans, max(W*y1, W*y2, W*y3)-min(W*y1, W*y2, W*y3))
    if W >= 3:
        x1 = int(round(W/3))
        x2 = (W-x1) // 2
        x3 = W - x1 - x2
        ans = min(ans, max(x1*H, x2*H, x3*H)-min(x1*H, x2*H, x3*H))
    
    # 縦にスライス + 残りに横にスライス
    x1_cand = [floor(W/3), ceil(W/3)]
    # x1_cand = [i for i in range(1, W)]
    y1 = H
    for x1 in x1_cand:
        x2 = W - x1
        x3 = x2
        y2 = H // 2
        y3 = H - y2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    # 横にスライス + 残りに縦にスライス
    y1_cand = [floor(H/3), ceil(H/3)]
    # y1_cand = [i for i in range(1, H)]
    x1 = W
    for y1 in y1_cand:
        y2 = H - y1
        y3 = y2
        x2 = W // 2
        x3 = W - x2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from math import floor, ceil

def main():
    H, W = map(int, readline().rstrip().split())
    ans = H * W
    if H >= 3:
        ans = min(ans, abs(W*(H//3) - W*(H-H//3*2)))
    if W >= 3:
        ans = min(ans, abs(H*(W//3) - H*(W-W//3*2)))
    
    # 縦にスライス + 残りに横にスライス
    # x1_cand = [floor(W/3), ceil(W/3)]
    x1_cand = [i for i in range(1, W)]
    y1 = H
    for x1 in x1_cand:
        x2 = W - x1
        x3 = x2
        y2 = H // 2
        y3 = H - y2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

        x2 = (W-x1) // 2
        x3 = (W-x1-x2)
        ans = min(ans, max((x1*H), (x2*H), (x3*H)) - min((x1*H), (x2*H), (x3*H)))

    # 横にスライス + 残りに縦にスライス
    # y1_cand = [floor(H/3), ceil(H/3)]
    y1_cand = [i for i in range(1, H)]
    x1 = W
    for y1 in y1_cand:
        y2 = H - y1
        y3 = y2
        x2 = W // 2
        x3 = W - x2
        ans = min(ans, max((x1*y1), (x2*y2), (x3*y3)) - min((x1*y1), (x2*y2), (x3*y3)))

        y2 = (H-y1) // 2
        y3 = (H-y1-y2)
        ans = min(ans, max((W*y1), (W*y2), (W*y3)) - min((W*y1), (W*y2), (W*y3)))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc(i, w, h):
	fixed = w * h
	a = w * i
	v_b = (h-i) // 2 * w
	v_c = fixed - a - v_b
	v_d = max(a, v_b, v_c) - min(a, v_b, v_c)
	h_b = w // 2 * (h-i)
	h_c = fixed - a - h_b
	h_d = max(a, h_b, h_c) - min(a, h_b, h_c)
	return min(v_d, h_d)

def resolve():
	h, w = map(int, input().split())
	ans = float('inf')
	for i in range(1, h):
		ans = min(ans, calc(i, w, h))
	for i in range(1, w):
		ans = min(ans, calc(i, h, w))
	print(ans)
resolve()

Submission status: Accepted

Solution code:
h , w = map(int, input().split())
mi=h*w
s=h*w
for i in range(h):
    s1=w*i
    if w%2==0 or (h-i)%2==0:
        s2=(s-s1)//2
        s3=s2
    elif h-i<w:
        s2=(h-i)*(w-1)//2
        s3=(h-i)*(w+1)//2
    else:
        s2=(h-i-1)//2*w
        s3=(h-i+1)//2*w
    d=abs(min(s1,s2,s3)-max(s1,s2,s3))
    if d<mi:
        mi=d
for i in range(w):
    s1=h*i
    if (w-i)%2==0 or h%2==0:
        s2=(s-s1)//2
        s3=s2
    elif w-i<h:
        s2=(w-i)*(h-1)//2
        s3=(w-i)*(h+1)//2
    else:
        s2=(w-i-1)//2*h
        s3=(w-i+1)//2*h
    d=abs(min(s1,s2,s3)-max(s1,s2,s3))
    if d<mi:
        mi=d
print(mi)

Submission status: Accepted

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

#縦に3つ分ける場合
if w % 3 == 0:
    s_tate = 0
else:
    s_tate = (int(w/3)+1) * h - int(w/3) * h

#横に3つに分ける場合
if h % 3 == 0:
    s_yoko = 0
else:
    s_yoko = (int(h/3)+1) * w - int(h/3) * w

#上側に縦に2つ、下方に1つでわける場合
case3 = INF
if w%2 == 0:
    for i in range(1,h):
        buf = abs((int(w/2) * i) - (w * (h-i)))
        case3 = min(buf, case3)
else:
    for i in range(1,h):
        buf1 = int(w/2) * i
        buf2 = (int(w/2)+1) * i
        buf3 = w * (h - i)
        buf = [buf1, buf2, buf3]
        buf = sorted(buf)
        sa = buf[2] - buf[0]
        case3 = min(sa, case3)

#左側に１つ、右側に横に２つでわける場合
case4 =INF
if h%2 == 0:
    for i in range(1,w):
        buf = abs((int(h/2) * i) - (h * (w-i)))
        case4 = min(buf, case4)
else:
    for i in range(1,w):
        buf1 = int(h/2) * i
        buf2 = (int(h/2)+1) * i
        buf3 = h * (w - i)
        buf = [buf1, buf2, buf3]
        buf = sorted(buf)
        sa = buf[2] - buf[0]
        case4 = min(sa, case4)
ans1 = min(s_tate, s_yoko)
ans2 = min(case3, case4)

ans = min(ans1, ans2)

#print(s_tate, s_yoko, case3, case4)

print(ans)

Submission status: Accepted

Solution code:
def calc(w, h):
	v = float('inf')
	a = w * h
	for i in range(1, h):
		h_a = w*i
		h_b = (h - i)//2*w
		h_c = a - h_a - h_b
		h_max = max(h_a, h_b, h_c)
		h_min = min(h_a, h_b, h_c)
		v = min(v, h_max - h_min)
		v_b = w//2*(h-i)
		v_c = a - h_a - v_b
		v_max = max(h_a, v_b, v_c)
		v_min = min(h_a, v_b, v_c)
		v = min(v, v_max - v_min)
	return v

def resolve():
	h, w = map(int, input().split())
	print(min(calc(h, w), calc(w, h)))
resolve()

Submission status: Accepted

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

if H*W%3 == 0:
    p1 = 0
else:
    p1 = min(H,W)
p.append(p1)

for i in range(1,W+1):
    a = i*H
    if H%2 == 0:
        b = (W-i)*(H//2)
        p2 = abs(a-b)
    else:
        b = (W-i)*(H//2)
        c = (W-i)*(H//2 +1)
        p2 = max(a,b,c)-min(a,b,c)
    p.append(p2)

for i in range(1,H+1):
    a = i*W
    if W%2 == 0:
        b = (H-i)*(W//2)
        p3 = abs(a-b)
    else:
        b = (H-i)*(W//2)
        c = (H-i)*(W//2 +1)
        p3 = max(a,b,c)-min(a,b,c)
    p.append(p3)

print(min(p))

Submission status: Accepted

Solution code:
def resolve():
    H, W = list(map(int, input().split()))
    
    def _solve(H, W):
        mean_w = W // 2
        ans = float("inf")
        for h in range(1, H):
            s1 = h * W
            mean_h = (H-h) // 2
            for i in range(0, 2):
                if i == 0:
                    s2 = (H-h)*mean_w
                    s3 = (H-h)*(W-mean_w)
                if i == 1:
                    s2 = mean_h*W
                    s3 = (H-h-mean_h)*W
                ans = min(ans, max(s1, s2, s3)-min(s1, s2, s3))
        return ans

    print(min(_solve(H, W), _solve(W, H)))

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
def min_value(w, h):
	ans = float('inf')
	for i in range(1, h):
		a = w*i
		v_t = (h-i)//2 * w
		v_b = (h-i)*w - v_t
		v_re = max(a, v_t, v_b) - min(a, v_t, v_b)
		h_l = (h-i)*(w//2)
		h_r = (h-i)*w-h_l
		h_re = max(a, h_l, h_r) - min(a, h_l, h_r)
		ans = min(ans, v_re, h_re)
	return ans

def resolve():
	h, w = map(int, input().split())
	a = min_value(w, h)
	b = min_value(h, w)
	print(min(a, b))
resolve()

Submission status: Accepted

Solution code:
from math import ceil


def main():
    H, W = map(int, input().split())
    if H*W % 3 == 0:
        print(0)
        return
    ans1 = float('inf')
    ans2 = float('inf')
    ans3 = min(H, W)
    # h == Tの上
    for h in range(1, H + 1):
        if W % 2 == 0:
            ans1 = min(ans1, abs(h*(W//2) - W*(H - h)))
        else:
            ans1 = min(
                ans1,
                max([
                    abs((h*(W//2) - W*(H - h))),
                    abs(h*((W + 1)//2) - W*(H - h)),
                    h
                ]))
    for w in range(1, W + 1):
        if H % 2 == 0:
            ans2 = min(ans2, abs(w*(H//2) - H*(W - w)))
        else:
            ans2 = min(
                ans2, max([abs((w*(H//2) - H*(W - w))), abs(w*((H + 1)//2) - H*(W - w)), w]))
    print(min([ans1, ans2, ans3]))
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = H*W
ans = 10**19
for w in range(1, W//2+1):
    s = w*H
    w2s = ((W-w)//2)*H
    h2s = (H//2)*(W-w)

    ws = [s, w2s, S-w2s-s]
    hs = [s, h2s, S-h2s-s]
    wm = max(ws)-min(ws)
    hm = max(hs)-min(hs)
    m = min(wm, hm)
    if m < ans:
        ans = m

H, W = W, H
for w in range(1, W//2+1):
    s = w*H
    w2s = ((W-w)//2)*H
    h2s = (H//2)*(W-w)

    ws = [s, w2s, S-w2s-s]
    hs = [s, h2s, S-h2s-s]
    wm = max(ws)-min(ws)
    hm = max(hs)-min(hs)
    m = min(wm, hm)
    if m < ans:
        ans = m
print(ans)

Submission status: Accepted

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

def sds(h,w):
    sdmin=h*w
    for hi in range(1,h):
        s1=hi*w
        s2=(h-hi)*(w//2)
        s3=(h-hi)*(w-w//2)
        sd=max(s1,s2,s3)-min(s1,s2,s3)
        sdmin=min(sdmin,sd)
    
        h2=(h-hi)//2
        s2=h2*w
        s3=(h-hi-h2)*w
        sd=max(s1,s2,s3)-min(s1,s2,s3)
        sdmin=min(sdmin,sd)

    return sdmin

print(min(sds(h,w),sds(w,h)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
mini=h*w
for i in range(1,h):
    if mini > max(w*(h-i),(w//2+w%2)*i) - min(w*(h-i),(w//2)*i):
        mini = max(w*(h-i),(w//2+w%2)*i) - min(w*(h-i),(w//2)*i)

for i in range(1,w):
    if mini > max(h*(w-i),(h//2+h%2)*i) - min(h*(w-i),(h//2)*i):
        mini = max(h*(w-i),(h//2+h%2)*i) - min(h*(w-i),(h//2)*i)

if h%3 == 0 or w%3 == 0:
    mini=0
else:
    if mini > h:
        mini = h
    elif mini > w:
        mini = w
    else:
        pass
print(mini)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    H, W = (int(_) for _ in input().split())
    INF = 10 ** 11

    def calc(h, w):
        # 縦に割る
        w1 = w // 2
        w2 = w - w1
        ret = INF
        for hh in range(1, h):
            ret = min(ret, max(w * hh, (h-hh)*w1, (h-hh)*w2) - min(w * hh, (h-hh)*w1, (h-hh)*w2))
        #横に割る
        for hh in range(1, h):
            h1 = (h-hh)//2
            h2 = h - hh - h1
            ret = min(ret, max(w*hh, w*h1, w*h2) - min(w*hh, w*h1, w*h2))
        return ret
    m1 = calc(H, W)
    m2 = calc(W, H)
    print(min(m1, m2))
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def calc(a, b):
    ret = a * b
    for i in range(1, a):
        area1 = b // 2 * i
        area2 = -(-b // 2) * i
        area3 = a * b - (area1 + area2)
        #print(area1, area2, area3)
        ret = min(ret, max(area1, area2, area3) - min(area1, area2, area3))
    return ret

if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    ans = h * w
    for i in range(1, max(h, w) - 1):
        area1 = min(h, w) * i
        area2 = min(h, w) * ((max(h, w) - i) // 2)
        area3 = min(h, w) * (-(-(max(h, w) - i) // 2))
        #print(area1, area2, area3)
        ans = min(ans, max(area1, area2, area3) - min(area1, area2, area3))
    print(min(calc(h, w), calc(w, h), 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()
def solve(p, q):
    r = int(p / 2)
    s = int(q / 3)
    a, b, c = p*s, r*(q-s), (p-r)*(q-s)
    ans = max(a, b, c) - min(a, b, c)
    a, b, c = p*(s+1), r*(q-s-1), (p-r)*(q-s-1)
    ans = min(ans, max(a, b, c) - min(a, b, c))
    return ans
ans = min(W, H, solve(H, W), solve(W, H))
print(ans)

Submission status: Accepted

Solution code:
# solution
# online help taken

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

if h%3==0 or w%3==0:
  ans=0
else:
  ans=min(h,w)
  
a=round(h/3)*w
b=(h-round(h/3))*(w//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
a=round(w/3)*h
b=(w-round(w/3))*(h//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
print(ans)