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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

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


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



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

    print(ans)


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=max(h,w)
    y=min(h,w)
    ans=y
    for hi in range(1,h):
        if hi*w>(h-hi)*((w+1)//2):
          ans=min(ans,abs((h-hi)*(w//2)-hi*w))
        elif hi*w<(h-hi)*((w+1)//2):
          ans=min(ans,abs((h-hi)*((w+1)//2)-hi*w))
        else:
          ans=min(ans,abs((h-hi)*((w+1)//2)-(h-hi)*(w//2)))
    for wi in range(1,w):
        if wi*h>(w-wi)*((h+1)//2):
          ans=min(ans,abs((w-wi)*(h//2)-wi*h))
        elif wi*h<(w-wi)*((h+1)//2):
          ans=min(ans,abs((w-wi)*((h+1)//2)-wi*h))
        else:
          ans=min(ans,abs((w-wi)*((h+1)//2)-(w-wi)*(h//2)))
    print(ans)

Submission status: Wrong Answer

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

def diff_min(L):
    len_L = len(L)
    ret = min([abs(L[i] - L[(i+1)%len_L]) for i in range(len_L)])
    return ret

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

    ans = 0
    if H % 3 != 0 and W % 3 != 0:
        # 同方向に分割する場合
        ans = min(H, W)

        # 分割方向を変える場合
        s = [0] * 3
        # 縦→横の場合と横→縦の場合
        for _ in range(2):
            s[0] = H * W // 3
            s[1] = (H * W - s[0]) // 2
            s[2] = (H * W - s[0]) - s[1]
            ans = min(diff_min(s), ans)
            s[0] = H * (W // 3 + 1)
            s[1] = (H * W - s[0]) // 2
            s[2] = (H * W - s[0]) - s[1]
            ans = min(diff_min(s), ans)
            H, W = W, H
       
    print(ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

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

Dif = 100000000

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

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

Submission status: Wrong Answer

Solution code:


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


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


def manhattan(p0, p1):
    return abs(p0[0]-p1[0])+abs(p0[1]-p1[1])

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

def _solve(H, W):
    if W%3 == 1:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3), H//2*(W-W//3), (H-H//2)*(W-W//3)),
                   max_diff(H*(W//3), H*(W//3), H*(W-(W//3)*2)))
    else:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3+2), H//2*(W-W//3-2), (H-H//2)*(W-W//3-2)),
                   max_diff(H*(W//3), H//2*(W-W//3), (H-H//2)*(W-W//3)),
                   max_diff(H*(W//3), H*(W//3), H*(W-(W//3)*2)))


def solve():
    """
    """
    H, W = read_ints()
    if H%3 == 0 or W%3 == 0:
        return 0
    return min(_solve(H, W), _solve(W, H))


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

Submission status: Wrong Answer

Solution code:


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


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


def manhattan(p0, p1):
    return abs(p0[0]-p1[0])+abs(p0[1]-p1[1])

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

def _solve(H, W):
    if W%3 == 1:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3), H//2*(W-W//3), (H-H//2)*(W-W//3)))
    else:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3+2), H//2*(W-W//3-2), (H-H//2)*(W-W//3-2)),
                   max_diff(H*(W//3), H//2*(W-W//3), (H-H//2)*(W-W//3)))


def solve():
    """
    """
    H, W = read_ints()
    if H%3 == 0 or W%3 == 0:
        return 0
    return min(_solve(H, W), _solve(W, H))


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

Submission status: Wrong Answer

Solution code:


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


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


def manhattan(p0, p1):
    return abs(p0[0]-p1[0])+abs(p0[1]-p1[1])

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

def _solve(H, W):
    if W%3 == 1:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3), H//2*(W-W//3), (H-H//2)*(W-W//3)))
    else:
        return min(max_diff(H*(W//3+1), H//2*(W-W//3-1), (H-H//2)*(W-W//3-1)),
                   max_diff(H*(W//3+2), H//2*(W-W//3-2), (H-H//2)*(W-W//3-2)))


def solve():
    """
    """
    H, W = read_ints()
    if H%3 == 0 or W%3 == 0:
        return 0
    return min(_solve(H, W), _solve(W, H))


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

    ans = H * W
    ans = min(ans, (H % 3) * W, (W % 3) * H)

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = H
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    S3 = H*W - S1 - S2
    diff1 = 1 << 50
    if S1 <= S3 <= S2:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    S3 = H*W - S1 - S2
    if S2 <= S3 <=  S1:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3:
        diff3 = abs(S3-S2)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    # if ans > mn:
    #     print(w,h_)
    #     print(diff1,diff2,diff2)
        
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    S3 = H*W - S1 - S2
    diff1 = 1 << 50
    if S1 <= S3 <= S2:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    S3 = H*W - S1 - S2
    if S2 <= S3 <=  S1:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3:
        diff3 = abs(S3-S2)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    # if ans > mn:
    #     print(w,h_)
    #     print(diff1,diff2,diff2)
        
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3 or S3 <= S1 <= S2:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = S1//(w_rest)
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = (S1-1)//(w_rest) + 1
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3 or S3 <= S1 <= S2:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = (S-1) // S1 + 1
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3 or S3 <= S1 <= S2:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = S // S1
    diff3 = 1 << 50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3 or S3 <= S1 <= S2:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().split())
# 横長で扱う
if H > W:
    H,W = W,H
ans = 1 << 50
# 横 or 縦分割
if H%3 == 0 or W%3 == 0:
    print(0)
    exit()
else:
    ans = W
# 横&縦
for w in range(1,W):
    S1 = w*H
    w_rest = W-w
    S = w_rest * H
    # S1が最小の場合: 大きい方のSをなるべく小さくする
    # よって切り上げ
    S2 = w_rest * ((H-1)//2+1)
    diff1 = 1 << 50
    if S2 > S1:
        diff1 = S2 - S1
    # S1が最大の場合: 小さい方のSをなるべく大きくする
    # よって切り捨て
    S2 = w_rest * (H//2)
    diff2 = 1 << 50
    if S1 > S2:
        diff2 = S1 - S2
    # S1が真ん中 : 大小の中で一番差が小さいやつ
    h_ = (S2-1) // S1 + 1
    diff3 = 1<<50
    S2 = w_rest * h_
    S3 = w_rest * (H-h_)
    if S2 <= S1 <= S3 or S3 <= S1 <= S2:
        diff3 = abs(S3-S2)
    # print("xhc",S1,S2,S3)
    mn = min(diff1,diff2,diff3)
    # print("w",w,"diffs",diff1,diff2,diff3)
    ans = min(ans,mn)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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


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

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

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

ans = H*W
hh = H%3
ww = W%3
if H>=3:
    ans = min(ans, W*hh)
if W>=3:
    ans = min(ans, H*ww)

ww1 = W//2
ww2 = W//2 + W%2
for i in range(1,H):
    v1,v2,v3 = ww1*i, ww2*i, W*(H-i)
    ans = min(ans, max(v1,v2,v3)-min(v1,v2,v3))

hh1 = H//2
hh2 = H//2 + H%2
for i in range(1,W):
    v1,v2,v3 = hh1*i, hh2*i, H*(W-i)
    ans = min(ans, max(v1,v2,v3)-min(v1,v2,v3))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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

ans = H*W
hh = H%3
ww = W%3
ans = min(ans, W*hh)
ans = min(ans, H*ww)

ww1 = W//2
ww2 = W//2 + W%2
for i in range(1,H):
    v1,v2,v3 = ww1*i, ww2*i, W*(H-i)
    ans = min(ans, max(v1,v2,v3)-min(v1,v2,v3))

hh1 = H//2
hh2 = H//2 + H%2
for i in range(1,W):
    v1,v2,v3 = hh1*i, hh2*i, H*(W-i)
    ans = min(ans, max(v1,v2,v3)-min(v1,v2,v3))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()

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

def divide_3(a, b):
    diff1, diff2 = INF, INF
    for i in range(-1, 2):
        p1 = (a//3+i) * b
        left_1 = H*W - p1
        p2 = b//2 * (a - (a//3+i))
        p3 = left_1 - p2
        diff_1 = max(p1, p2, p3) - min(p1, p2, p3)
        diff1 = min(diff1, diff_1)

        q1 = (ceil(a/3)+i) * b
        left_2 = H*W - q1
        q2 = b//2 * (a - (ceil(a/3)+i))
        q3 = left_2 - q2
        diff_2 = max(q1, q2, q3) - min(q1, q2, q3)
        diff2 = min(diff2, diff_2)

    return min(diff1, diff2)

print(min(divide_3(H, W), divide_3(W, H)))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    H, W = in_nn()

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

    ans = 10 ** 9 + 7

    if H > 3:
        ans = min(ans, W)

    if W > 3:
        ans = min(ans, H)

    for i in range(-2, 3):
        i = H // 3 + i
        for j in range(-2, 3):
            j = W // 2 + j
            if 0 < i < H - 1 and 0 < j < W:
                a1 = i * W
                a2 = (H - i) * j
                a3 = (H - i) * (W - j)
                ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))

    for i in range(-2, 3):
        i = H // 2 + i
        for j in range(-2, 3):
            j = W // 3 + j
            if 0 < i < H - 1 and 0 < j < W:
                a1 = j * H
                a2 = (W - j) * i
                a3 = (W - j) * (H - i)
                ans = min(ans, max(a1, a2, a3) - min(a1, a2, a3))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = 10**8
if h%3==0 or w%3==0:
  print(0)
  exit()
else:
  for i in range(1,w):
    a = h*i
    if h%2==0:
      b = (w-i)*(h//2)
      s = min(s,abs(b-a))
    else:
      b = (w-i)*(h//2)
      c = (w-i)*(h//2+1)
      a,b,c = sorted(list([a,b,c]))
      s = min(s,c-a)
      
  for i in range(1,h):
    a = w*i
    if w%2==0:
      b = (h-i)*(w//2)
      s = min(s,abs(b-a))
    else:
      b = (h-i)*(w//2)
      c = (h-i)*(w//2+1)
      a,b,c = sorted(list([a,b,c]))
      s = min(s,c-a)
  print(s)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = 10**8
if h%3==0 or w%3==0:
  print(0)
  exit()
else:
  h,w = min(h,w),max(h,w)
  for i in range(1,w):
    a = h*i
    if h%2==0:
      b = (w-i)*(h//2)
      s = min(s,abs(b-a))
    else:
      b = (w-i)*(h//2)
      c = (w-i)*(h//2+1)
      a,b,c = sorted(list([a,b,c]))
      s = min(s,c-a)
print(s)

Submission status: Wrong Answer

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

def f():
    if H % 3 == 0:
        return 0
    
    r = 10 ** 18
    for i in range(1, H):
        s1 = i * W
        if W % 2 == 0:
            s2 = s3 = (H - i) * (W // 2)
        else:
            s2 = (H - i) * (W // 2)
            s3 = (H - i) * (W - W // 2)
        r = min(r, max(s1, s2, s3) - min(s1, s2, s3))
    
    return r

res = f()
H, W = W, H
res = min(res, f())
print(res)

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()
if H == 1 or W == 1:
    print(1)
    exit()
ans = 1 << 30
w = W//2
for h in range(1, H+1):
    s1 = w*h
    s2 = (W-w)*h
    s3 = W*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
W, H = H, W
w = W//2
for h in range(1, H+1):
    s1 = w*h
    s2 = (W-w)*h
    s3 = W*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
print(ans)

Submission status: Wrong Answer

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

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

S = H * W
a = (S // 3 // H) - 10
b = (S // 3 // W) - 10

ans1 = float('inf')
ans2 = float('inf')
for i in range(a, a + 30):
    if i <= 0 or i >= W:
        continue
    x = i * H
    y = (W - i) * (H//2)
    z = S - x - y
    ans1 = min(ans1, max(x, y, z) - min(x, y, z))

for i in range(b, b + 30):
    if i <= 0 or i >= H:
        continue
    x = i * W
    y = (H - i) * (W//2)
    z = S - x - y
    ans2 = min(ans2, max(x, y, z) - min(x, y, z))
print(min(ans1, ans2))

Submission status: Wrong Answer

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

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

S = H * W
a = (S // 3 // H) - 10
b = (S // 3 // W) - 10

ans1 = float('inf')
ans2 = float('inf')
for i in range(a, a + 30):
    x = i * H
    y = (W - i) * (H//2)
    z = S - x - y
    ans1 = min(ans1, max(x, y, z) - min(x, y, z))

for i in range(b, b + 30):
    x = i * W
    y = (H - i) * (W//2)
    z = S - x - y
    ans2 = min(ans2, max(x, y, z) - min(x, y, z))
print(min(ans1, ans2))

Submission status: Wrong Answer

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

h,w=min(h,w),max(h,w)
ans=float('inf')
for i in range(1,w):
    s1=h*i
    neww=w-i
    newh,neww=min(h,neww),max(h,neww)
    if newh%2==0 or neww%2==0:
        s2=(newh*neww)//2
        s3=first-(s1+s2)
        s4=(newh*neww)//2
        s5=first-(s1+s2)
    else:
        s2=newh*(neww//2)
        s3=first-(s1+s2)
        s4=(newh//2)*neww
        s5=first-(s1+s4)
    #print(s1,s2,s3)
    ans=min(ans,max([s1,s2,s3])-min([s1,s2,s3]), max([s1,s4,s5])-min([s1,s4,s5]))
print(ans)

Submission status: Wrong Answer

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

h,w=min(h,w),max(h,w)
ans=float('inf')
for i in range(1,w):
    s1=h*i
    neww=w-i
    newh,neww=min(h,neww),max(h,neww)
    if newh%2==0 or neww%2==0:
        s2=newh*neww//2
        s3=first-(s1+s2)
    else:
        s2=newh*(neww//2)
        s3=first-(s1+s2)
    #print(s1,s2,s3)
    ans=min(ans,max([s1,s2,s3])-min([s1,s2,s3]))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
    exit()
h,w=min(h,w),max(h,w)
first=h*w
x=(w+int(w%3==2))//3
s1=h*x
w-=x
h,w=min(h,w),max(h,w)
if h%2==0 or w%2==0:
    s2=h*w//2
    s3=h*w//2
else:
    s2=h*(w//2)
    s3=first-(s1+s2)
#print(s1,s2,s3)
print(max([s1,s2,s3])-min([s1,s2,s3]))

Submission status: Wrong Answer

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

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

a=h//2
b=h-a
for i in range(1,w):
    length=w-i
    A=i*a
    B=i*b
    peace_max=max(length*h,A,B)
    peace_min=min(length*h,A,B)
    ans=min(ans,peace_max-peace_min)

a=w//2
b=w-a
for i in range(1,h):
    length=h-i
    A=i*a
    B=i*b
    peace_max=max(length*w,A,B)
    peace_min=min(length*w,A,B)
    ans=min(ans,peace_max-peace_min)

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = float('inf')
    for h in range(1, H):
        Sa = h*W
        Sb = (H-h)*(W//2)
        Sc = (H-h)*(W//2+W%2)
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
        
    for w in range(1, W):
        Sa = w*H
        Sb = (W-w)*(H//2)
        Sc = (W-w)*(H//2+H%2)
        tmp = sorted([Sa, Sb, Sc])
        ans = min(tmp[-1]-tmp[0], ans)
        
    print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    Smax = (max(H, W) // 3 + max(H, W)%2) * min(H, W)
    Smin = (max(H, W) - max(H, W) // 3 - max(H, W)%2) * (min(H, W) // 2)
    print(abs(Smax-Smin))

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    def calc_diff(h, w):
        diff = 10**9
        for i in range(1, ceil(w/2)+1):
            a = i*h
            b  = (w-i)*floor(h/2)
            c  = (w-i)*ceil(h/2)
            diff = min(diff, max(a, b, c) - min(a, b, c))
        return diff
    diff1 = calc_diff(h, w)
    diff2= calc_diff(w, h)
    print(min(diff1, diff2))

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

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

if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    def calc_diff(h, w):
        a = ceil(h / 3) * w
        b = (h - ceil(h / 3)) * floor(w // 2)
        c = (h - ceil(h / 3)) * ceil(w / 2)
        diff = abs(max(a, b, c) - min(a, b, c))
        a = floor(h / 3) * w
        b = (h - floor(h / 3)) * floor(w / 2)
        c = (h - floor(h / 3)) * ceil(w / 2)
        diff = min(diff, max(a, b, c) -min(a, b,c))
        return diff
    diff1 = calc_diff(h, w)
    diff2= calc_diff(w, h)
    print(min(diff1, diff2))