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 math import ceil, floor


def main():
    h, w = map(int, input().split())
    d = h * w
    d = min((ceil(h / 3) - floor(h / 3)) * w, d)
    d = min((ceil(w / 3) - floor(w / 3)) * h, d)
    dd = h * w
    for i in range(h):
        u = i * w
        d1 = (h - i) * ceil(w / 2)
        d2 = (h - i) * floor(w / 2)
        di = max(abs(u - d1), abs(u - d2))
        if di > dd:
            break
        dd = di
    d = min(dd, d)
    dd = h * w
    for i in range(w):
        u = i * h
        d1 = (w - i) * ceil(h / 2)
        d2 = (w - i) * floor(h / 2)
        di = max(abs(u - d1), abs(u - d2))
        if di > dd:
            break
        dd = di
    d = min(dd, d)
    print(d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
if w%3==0:
    s1=0
else:
    s1=h
if h%3==0:
    s2=0
else:
    s2=w
fw=floor(w/3)
fh=floor(h/2)
cw=ceil(w/3)
SMAX1=(w-fw)*(h-fh)
SMIN1=min(fw*h,(w-fw)*fh)
SMAX2=max(cw*h,(w-cw)*(h-fh))
SMIN2=(w-cw)*fh
#print(SMAX1,SMIN1,SMAX2,SMIN2)
s3=min(SMAX1-SMIN1,SMAX2-SMIN2)
h,w=w,h
fw=floor(w/3)
fh=floor(h/2)
cw=ceil(w/3)
SMAX1=(w-fw)*(h-fh)
SMIN1=min(fw*h,(w-fw)*fh)
SMAX2=max(cw*h,(w-cw)*(h-fh))
SMIN2=(w-cw)*fh
s4=min(SMAX1-SMIN1,SMAX2-SMIN2)
#print(s1,s2,s3,s4)
ans=min(s1,s2,s3,s4)
print(ans)

Submission status: Accepted

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

ans = float('inf')

# first cut vertical
for x in range(1, W):
  S1 = x * H
  # cut vertical
  w2 = (W - x) // 2
  w3 = W - x - w2
  S2 = w2 * H
  S3 = w3 * H
  S_max = max(S1, S3)
  S_min = min(S1, S2)
  ans = min(ans, S_max - S_min)
  # cut horizontal
  h2 = H // 2
  h3 = H - h2
  S2 = (W - x) * h2
  S3 = (W - x) * h3
  S_max = max(S1, S3)
  S_min = min(S1, S2)
  ans = min(ans, S_max - S_min)
# first cut horizontal
for y in range(1, H):
  S1 = W * y
  # cut vertical
  w2 = W // 2
  w3 = W - w2
  S2 = w2 * (H - y)
  S3 = w3 * (H - y)
  S_max = max(S1, S3)
  S_min = min(S1, S2)
  ans = min(ans, S_max - S_min)
  # cut horizontal
  h2 = (H - y) // 2
  h3 = H - y - h2
  S2 = W * h2
  S3 = W * h3
  S_max = max(S1, S3)
  S_min = min(S1, S2)
  ans = min(ans, S_max - S_min)

print(int(ans))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    num1=max((h//3)*w,(h-(h//3))*(w//2),(h-(h//3))*(w-(w//2)))-min((h//3)*w,(h-(h//3))*(w//2),(h-(h//3))*(w-(w//2)))
    num2=max((w//3)*h,(w-(w//3))*(h//2),(w-(w//3))*(h-(h//2)))-min((w//3)*h,(w-(w//3))*(h//2),(w-(w//3))*(h-(h//2)))
    num3=max((h//3+1)*w,(h-(h//3+1))*(w//2),(h-(h//3+1))*(w-(w//2)))-min((h//3+1)*w,(h-(h//3+1))*(w//2),(h-(h//3+1))*(w-(w//2)))
    num4=max((w//3+1)*h,(w-(w//3+1))*(h//2),(w-(w//3+1))*(h-(h//2)))-min((w//3+1)*h,(w-(w//3+1))*(h//2),(w-(w//3+1))*(h-(h//2)))
    print(min(num1,num2,num3,num4,h,w))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ans = 10**18
if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()
if h > 3:
    maxs = (h//3+1)*w
    mins = (h//3)*w
    ans = min(maxs-mins,ans)
if w > 3:
    maxs = (w//3+1)*h
    mins = (w//3)*h
    ans = min(ans,maxs-mins)
for i in range(1,h):
    a = i*w
    b = (h-i)*(w//2)
    c = (h-i)*(w-(w//2))
    maxs = max(max(a,b),c)
    mins = min(min(a,b),c)
    ans = min(ans,maxs-mins)
for i in range(1,w):
    a = i*h
    b = (w-i)*(h//2)
    c = (w-i)*(h-(h//2))
    maxs = max(max(a,b),c)
    mins = min(min(a,b),c)
    ans = min(ans,maxs-mins)
print(ans)

Submission status: Accepted

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

dif = 10**10

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

for i in range(H):
	a = i*W
	h = (H-i)//2
	abc = [a, h*W, (H-i-h)*W]
	if not(0 in abc):
		dif = min(dif, max(abc)-min(abc))
	
	h = H-i
	w = W//2
	abc = [a, h*w, h*(W-w)]
	if not(0 in abc):
		dif = min(dif, max(abc)-min(abc))

for i in range(W):
	a = H*i
	w = (W-i)//2
	abc = [a, H*w, H*(W-i-w)]
	if not(0 in abc):
		dif = min(dif, max(abc)-min(abc))
	
	w = W-i
	h = H//2
	abc = [a, h*w, (H-h)*w]
	if not(0 in abc):
		dif = min(dif, max(abc)-min(abc))

print(dif)

Submission status: Accepted

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

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()

ans = INF
for i in range(1,H):
  a = i*W
  if H-i>=2:
    b = ((H-i)//2)*W
    c = -(-(H-i)//2)*W
    ans = min(ans,max(a,b,c)-min(a,b,c))
  if W >= 2:
    b = (W//2)*(H-i)
    c = -(-W//2)*(H-i)
    ans = min(ans,max(a,b,c)-min(a,b,c))
for i in range(1,W):
  a = i*H
  if W-i>=2:
    b = ((W-i)//2)*H
    c = -(-(W-i)//2)*H
    ans = min(ans,max(a,b,c)-min(a,b,c))
  if H >= 2:
    b = (H//2)*(W-i)
    c = -(-H//2)*(W-i)
    ans = min(ans,max(a,b,c)-min(a,b,c))
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()

ans = INF
for i in range(1,H):
  a = i*W
  if H-i>=2:
    b = ((H-i)//2)*W
    c = (H-i)*W-b
    ans = min(ans,max(a,b,c)-min(a,b,c))
  if W >= 2:
    b = (W//2)*(H-i)
    c = (H-i)*W-b
    ans = min(ans,max(a,b,c)-min(a,b,c))
for i in range(1,W):
  a = i*H
  if W-i>=2:
    b = ((W-i)//2)*H
    c = (W-i)*H-b
    ans = min(ans,max(a,b,c)-min(a,b,c))
  if H >= 2:
    b = (H//2)*(W-i)
    c = (W-i)*H-b
    ans = min(ans,max(a,b,c)-min(a,b,c))
print(ans)

Submission status: Accepted

Solution code:
def aaa(a, b):
    return abs((a // 3 * b) - ((a // 3 + 1) * b))


def bbb(a, b):
    ret = 1000 * 100
    for x in range(1, a):
        xx = a - x
        i = x * b
        j = xx * (b // 2)
        k = xx * (b // 2 + (b % 2))
        tmp = max(abs(i - j), abs(j - k), abs(k - i))
        ret = min(ret, tmp)
    return ret


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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    a = aaa(H, W)
    b = aaa(W, H)
    c = bbb(H, W)
    d = bbb(W, H)
    print(min(a, b, c, d))

Submission status: Accepted

Solution code:
from math import floor, ceil
H, W = map(int, input().split())

ans = float('inf')
for h in range(1, H+1):
    A = h * W
    B = floor((H-h) / 2) * W
    C = ceil((H-h) / 2) * W
    B2 = (H-h) * floor(W / 2)
    C2 = (H-h) * ceil(W / 2)
    ans = min(ans, max([A, B, C]) - min([A, B, C]))
    ans = min(ans, max([A, B2, C2]) - min([A, B2, C2]))

for w in range(1, W+1):
    A = H * w
    B = floor((W-w) / 2) * H
    C = ceil((W-w) / 2) * H
    B2 = (W-w) * floor(H / 2)
    C2 = (W-w) * ceil(H / 2)
    ans = min(ans, max([A, B, C]) - min([A, B, C]))
    ans = min(ans, max([A, B2, C2]) - min([A, B2, C2]))

print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def calc_T_form(h, w):
        left = w // 2
        right = w - left
        ans = inf
        for i in range(1, h):
            sa, sb, sc = i * w, (h-i) * left, (h-i) * right
            ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
        return ans
    
    def calc_rotateT_form(h, w):
        up = h // 2
        down = h - h//2
        ans = inf
        for i in range(1, w):
            sa, sb, sc = i * h, (w-i) * up, (w-i) * down
            ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
        return ans
    
    def calc_slice(h, w):
        return min((h//3+1)*w - (h//3)*w, (w//3+1)*h - (w//3)*h)

    
    h, w = mi()
    if h * w % 3 == 0:
        print(0)
    else:
        print(min(calc_T_form(h, w), calc_rotateT_form(h, w), calc_slice(h, w)))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def pattern1(A, B):
    s1 = (A // 3) * B
    s2 = ((A - (A // 3)) // 2) * B
    s3 = A * B - s1 - s2
    return max([abs(s1 - s2), abs(s2 - s3), abs(s3 - s1)])


def pattern2(A, B):
    a1 = A // 2
    a2 = A - a1
    b1 = (2 * B + 1) // 3
    b2 = B - b1
    s1, s2, s3 = a1 * b1, a2 * b1, A * b2
    return max([abs(s1 - s2), abs(s2 - s3), abs(s3 - s1)])


def main():
    H, W = list(map(int, input().split(' ')))
    ans = min([
        pattern1(H, W),
        pattern1(W, H),
        pattern2(H, W),
        pattern2(W, H)
    ])
    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:
  temp=[w,h]
  if h%2==0 and w%2==0:
    temp.append(abs(int(w//3+1)*h-int(w-w//3-1)*int(h//2)))
    temp.append(abs(int(w//3)*h-int(w-w//3)*int(h//2)))        
    temp.append(abs(int(h//3+1)*w-int(h-h//3-1)*int(w//2)))
    temp.append(abs(int(h//3)*w-int(h-h//3)*int(w//2)))  
  elif h%2==0:
    temp.append(max(int(h//3*w),int(h-h//3)*int(w//2),int(h-h//3)*int(w//2+1))-min(int(h//3*w),int(h-h//3)*int(w//2),int(h-h//3)*int(w//2+1)))
    temp.append(max(int(h//3+1)*w,int(h-h//3-1)*int(w//2),int(h-h//3-1)*int(w//2+1))-min(int(h//3+1)*w,int(h-h//3-1)*int(w//2),int(h-h//3-1)*int(w//2+1)))
    temp.append(abs(int(w//3+1)*h-int(w-w//3-1)*int(h//2)))
    temp.append(abs(int(w//3)*h-int(w-w//3)*int(h//2)))             
  elif w%2==0:
    temp.append(max(int(w//3*h),int(w-w//3)*int(h//2),int(w-w//3)*int(h//2+1))-min(int(w//3*h),int(w-w//3)*int(h//2),int(w-w//3)*int(h//2+1)))
    temp.append(max(int(w//3+1)*h,int(w-w//3-1)*int(h//2),int(w-w//3-1)*int(h//2+1))-min(int(w//3+1)*h,int(w-w//3-1)*int(h//2),int(w-w//3-1)*int(h//2+1)))
    temp.append(abs(int(h//3+1)*w-int(h-h//3-1)*int(w//2)))
    temp.append(abs(int(h//3)*w-int(h-h//3)*int(w//2)))                
  else:
    temp.append(max(int(h//3*w),int(h-h//3)*int(w//2),int(h-h//3)*int(w//2+1))-min(int(h//3*w),int(h-h//3)*int(w//2),int(h-h//3)*int(w//2+1)))
    temp.append(max(int(h//3+1)*w,int(h-h//3-1)*int(w//2),int(h-h//3-1)*int(w//2+1))-min(int(h//3+1)*w,int(h-h//3-1)*int(w//2),int(h-h//3-1)*int(w//2+1)))
    temp.append(max(int(w//3*h),int(w-w//3)*int(h//2),int(w-w//3)*int(h//2+1))-min(int(w//3*h),int(w-w//3)*int(h//2),int(w-w//3)*int(h//2+1)))
    temp.append(max(int(w//3+1)*h,int(w-w//3-1)*int(h//2),int(w-w//3-1)*int(h//2+1))-min(int(w//3+1)*h,int(w-w//3-1)*int(h//2),int(w-w//3-1)*int(h//2+1)))
  print(min(temp))

Submission status: Accepted

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


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

        # Hを1:2で分割
        for i in range(3):
            d = (H // 3)- 1 + i
            if d > 0:
                choco = [d * W, (H-d) * (W//2), (H-d) * (W - W//2)]
                ans = min(ans, max(choco) - min(choco))
        
        # Wを1:2で分割
        for i in range(3):
            d = (W // 3)- 1 + i
            if d > 0:
                choco = [d * H, (W-d) * (H//2), (W-d) * (H - H//2)]
                ans = min(ans, max(choco) - min(choco))
        
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():
        H, W = map(int, input().split())
        if H % 3 == 0 or W % 3 == 0:
            return 0
        else:
            ans = 10**18

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

                B = (W//2)*(H-h)
                C = (W-(W//2))*(H-h)
                ans = min(max(A, B, C) -
                          min(A, B, C), ans)

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

                B = (H//2)*(W-w)
                C = (H-(H//2))*(W-w)
                ans = min(max(A, B, C) -
                          min(A, B, C), ans)
            return ans
    print(main())


resolve()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
h, w = map(int, input().split())

ans1 = INF
ans2 = INF
ans3 = INF
ans4 = INF

if h % 3 == 0:
    ans1 = 0
else:
    ans1 = w

if w % 3 == 0:
    ans2 = 0
else:
    ans2 = h

for i in range(1, w):
    if h % 2 == 0:
        ans3 = min(ans3, abs(h * i - (w - i) * h // 2))
    else:
        a = h * i
        b = (w - i) * (h // 2)
        c = (w - i) * (-(-h // 2))
        ans3 = min(ans3, max(a, b, c) - min(a, b, c))

for i in range(1, h):
    if w % 2 == 0:
        ans3 = min(ans3, abs(w * i - (h - i) * w // 2))
    else:
        a = w * i
        b = (h - i) * (w // 2)
        c = (h - i) * (-(-w // 2))
        ans3 = min(ans3, max(a, b, c) - min(a, b, c))

ans = min(ans1, ans2, ans3, ans4)
print(ans)

Submission status: Accepted

Solution code:
import sys

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


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

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

    res = f_inf
    for h in range(H):
        A = h * W

        B = W * ((H - h) // 2)
        C = W * ((H - h) - (H - h) // 2)
        ma = max(A, B, C)
        mi = min(A, B, C)
        res = min(res, ma - mi)

        B = (H - h) * (W // 2)
        C = (H - h) * (W - W // 2)
        ma = max(A, B, C)
        mi = min(A, B, C)
        res = min(res, ma - mi)

    for w in range(W):
        A = w * H

        B = H * ((W - w) // 2)
        C = H * ((W - w) - (W - w) // 2)
        ma = max(A, B, C)
        mi = min(A, B, C)
        res = min(res, ma - mi)

        B = (W - w) * (H // 2)
        C = (W - w) * (H - H // 2)
        ma = max(A, B, C)
        mi = min(A, B, C)
        res = min(res, ma - mi)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ans = H*W
#縦に3つ切る
if(W%3 == 0):
  ans = 0
else:
  ans = min(ans, H)

#横に3つ切る
if(H%3 == 0):
  ans = 0
else:
  ans = min(ans, W)
  
#始め縦に切り、その後二等分する
if(H % 2 == 0):
  sa = W*H//2
  sb = W*H//2
  sc = 0
  ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
  for i in range(W-1):
    sc += H
    sa -= H//2
    sb -= H//2
    ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
else:
  sa = W * (H//2)
  sb = W * (H//2 + 1)
  sc = 0
  ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
  for i in range(W-1):
    sc += H
    sa -= H//2
    sb -= H//2 + 1
    ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
    
#始め横に切り、その後二等分する
if(W % 2 == 0):
  sa = W*H//2
  sb = W*H//2
  sc = 0
  ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
  for i in range(H-1):
    sc += W
    sa -= W//2
    sb -= W//2
    ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
else:
  sa = H * (W//2)
  sb = H * (W//2 + 1)
  sc = 0
  ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
  for i in range(W-1):
    sc += W
    sa -= W//2
    sb -= W//2 + 1
    ans = min(ans, max(sa, sb, sc) - min(sa, sb, sc))
    
print(ans)