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 result_dividing_by_a_direction(x, y):
    return abs(x // 3 - (x - 2 * (x // 3))) * y


def result_dividing_2plus1(x, y, d):
    area1 = x * d
    area2 = (y - d) * (x // 2)
    area3 = (y - d) * (x - (x // 2))
    return max(area1, area2, area3) - min(area1, area2, area3)


def main():
    h, w = map(int, input().split())
    ans = result_dividing_by_a_direction(h, w)
    ans = min(result_dividing_by_a_direction(w, h), ans)
    for d in range(1, w):
        ans = min(result_dividing_2plus1(h, w, d), ans)
    for d in range(1, h):
        ans = min(result_dividing_2plus1(w, h, d), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ans = 10**9
if h % 3 == 0 or w % 3 == 0:
    ans = 0
else:
    for width in range(1, w):
        left = width * h
        if h % 2 == 0:
            right_up   = (w-width)*(h//2)
            right_down = right_up
        else:
            right_up   = (w-width)*(h//2+1)
            right_down = (w-width)*(h//2)
        ans = min(ans, max(left, right_up, right_down) - min(left, right_up, right_down))
    for height in range(1, h):
        up = w * height
        if w % 2 == 0:
            down_left  =  (w//2)*(h-height)
            down_right =  down_left
        else:
            down_left  =  (w//2)*(h-height)
            down_right =  (w//2+1)*(h-height)
        ans = min(ans, max(up, down_left, down_right) - min(up, down_left, down_right))

print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ans = h*w
for i in range(1,h-1):
    A = w*i
    if w%2 == 0 or (h-i)%2 == 0:
        B = ((h-i)*w)//2
        C = ((h-i)*w)//2
    else:
        if h-i <= w:
            B = (h-i)*((w//2)+1)
            C = (h-i)*(w//2)
        else:
            B = ((h-i)//2 + 1) * w
            C = ((h-i)//2) * w
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))

for i in range(1,w-1):
    A = h*i
    if (w-i)%2 == 0 or h%2 == 0:
        B = ((w-i)*h)//2
        C = ((w-i)*h)//2
    else:
        if w-i <= h:
            B = (w-i)*((h//2)+1)
            C = (w-i)*(h//2)
        else:
            B = ((w-i)//2 + 1) * h
            C = ((w-i)//2) * h
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ans = h*w
for i in range(1,h-1):
    A = w*i
    if w%2 == 0 or (h-i)%2 == 0:
        B = (h-i)*w//2
        C = (h-i)*w//2
    else:
        if h-i <= w:
            B = (h-i)*((w//2)+1)
            C = (h-i)*(w//2)
        else:
            B = ((h-i)//2 + 1) * w
            C = (h-i)//2 * w
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))

for i in range(1,w-1):
    A = h*i
    if (w-i)%2 == 0 or h%2 == 0:
        B = (w-i)*h//2
        C = (w-i)*h//2
    else:
        if w-i <= h:
            B = (w-i)*((h//2)+1)
            C = (w-i)*(h//2)
        else:
            B = ((w-i)//2 + 1) * h
            C = (w-i)//2 * h
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ans = h*w
for i in range(1,h-1):
    A = w*i
    if w%2 == 0 or (h-i)%2 == 0:
        B = (h-i)*w//2
        C = (h-i)*w//2
    else:
        if h-1 < w:
            B = (h-i)*((w//2)+1)
            C = (h-i)*(w//2)
        else:
            B = ((h-i)//2 + 1) * w
            C = (h-i)//2 * w
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))

for i in range(1,w-1):
    A = h*i
    if (w-i)%2 == 0 or h%2 == 0:
        B = (w-i)*h//2
        C = (w-i)*h//2
    else:
        if w-1 < h:
            B = (w-i)*((h//2)+1)
            C = (w-i)*(h//2)
        else:
            B = ((w-i)//2 + 1) * h
            C = (w-i)//2 * h
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ans = h*w
for i in range(1,h-1):
    A = w*i
    if w%2 == 0 or h-1%2 == 0:
        B = (h-i)*w//2
        C = (h-i)*w//2
    else:
        if h-1 < w:
            B = (h-i)*((w//2)+1)
            C = (h-i)*(w//2)
        else:
            B = ((h-i)//2 + 1) * w
            C = (h-i)//2 * w
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))

for i in range(1,w-1):
    A = h*i
    if w%2 == 0 or h-1%2 == 0:
        B = (w-i)*h//2
        C = (w-i)*h//2
    else:
        if w-1 < h:
            B = (w-i)*((h//2)+1)
            C = (w-i)*(h//2)
        else:
            B = ((w-i)//2 + 1) * h
            C = (w-i)//2 * h
    ans = min(ans,max(A,max(B,C)) - min(A,min(B,C)))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def core(h, H, W):
    if W % 2 == 0:
        return abs(h * W - (H - h) * (W // 2))
    else:
        a, b, c = h * W, (H - h) * (W // 2), (H - h) * (W // 2 + 1)
        return max(abs(a - b), abs(b - c), abs(c - a))


def solve(H, W):
    ans = abs((H // 3) * W - ((H + 2) // 3) * W)
    ans = min(ans, core(H // 3, H, W))

    return ans


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

    ans = min(solve(H, W), solve(W, H))

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a1=min(h,w)
a2=10**6
a3=10**6
for i in range(1,h):
  mx=max(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  mn=min(w*i,(w//2)*(h-i),((w+1)//2)*(h-i))
  a2=min(a2,mx-mn)
for j in range(1,w):
  mx=max(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  mn=min(h*i,(h//2)*(w-i),((h+1)//2)*(w-i))
  a3=min(a3,mx-mn)
print(min(a1,a2,a3))

Submission status: Wrong Answer

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

ans = 10**10

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

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

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

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()

ans = float('inf')

#縦割り+横半分
for x in range(1, w+1):
    tate_area = x*h
    yoko_min_area = (w-x)*(h//2)
    if h%2 == 1:
        yoko_max_area = (w-x)*(1+h//2)
    else:
        yoko_max_area = yoko_min_area
    area_max = max(tate_area, yoko_min_area, yoko_max_area)
    area_min = min(tate_area, yoko_min_area, yoko_max_area)
    ans = min(ans, area_max-area_min)
    #print(ans, tate_area, yoko_min_area, yoko_max_area)

#横割り+縦半分
for y in range(h//3, h+1):
    yoko_area = y*w
    tate_min_area = (h-y)*(w//2)
    if w%2 == 1:
        tate_max_area = (h-y)*(1+w//2)
    else:
        tate_max_area = tate_min_area
    area_max = max(yoko_area, tate_min_area, tate_max_area)
    area_min = min(yoko_area, tate_min_area, tate_max_area)
    ans = min(ans, area_max-area_min)
    #print(ans, yoko_area, tate_min_area)
print(ans)

Submission status: Wrong Answer

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

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

else:
    s = []
    for i in range(1,H//2 +1):
        j = W//2
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
    for i in range(1,W//2 +1):
        j = H//2
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)
    for i in range(1,H//3+1):
        a = [W*i,W*(H-i)//2,(W*(H-i)//2+1)]
        b = max(a) - min(a)
        s.append(b)
    for i in range(1,W//3+1):
        a = [H*i,H*(W-i)//2,(H*(W-i)//2+1)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

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

s = []
for i in range(1,H//2 +1):
    j = W//2
    a = [i*W,j*(H-i),(W-j)*(H-i)]
    b = max(a) - min(a)
    s.append(b)
for i in range(1,W//2 +1):
    j = H//2
    a = [H*i,(W-i)*j,(W-i)*(H-j)]
    b = max(a) - min(a)
    s.append(b)
for i in range(1,H//3+1):
    a = [W*i,W*(H-i)//2,(W*(H-i)//2+1)]
    b = max(a) - min(a)
    s.append(b)
for i in range(1,W//3+1):
    a = [H*i,H*(W-i)//2,(H*(W-i)//2+1)]
    b = max(a) - min(a)
    s.append(b)
    
print(min(s))

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,H//2 +1):
        j = W//2
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
    for i in range(1,W//2+1):
        j = H//2
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,max(H,W)//2 +1):
        j = W//2
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
        j = H//2
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,int(H/2)+1):
        j = int(W/2)
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
        j = int(H/2)
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,math.ceil(H/2)+1):
        if W % 2 == 0:
            j = W/2
        else:
            j = math.ceil(W/2)
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
        if H % 2 == 0:
            j = H/2
        else:
            j = math.ceil(H/2)
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

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

if H % 3 == 0 or W % 3 == 0:
    print(0)
else:
    s = []
    for i in range(1,math.ceil(H/2)+1):
        if W % 2 == 0:
            j = W/2
        else:
            j = math.ceil(H/2)
        a = [i*W,j*(H-i),(W-j)*(H-i)]
        b = max(a) - min(a)
        s.append(b)
        if H % 2 == 0:
            j = H/2
        else:
            j = math.ceil(H/2)
        a = [H*i,(W-i)*j,(W-i)*(H-j)]
        b = max(a) - min(a)
        s.append(b)

    print(min(s))

Submission status: Wrong Answer

Solution code:
def answer(H,W,ans):
    for x in range(1,W):
        y1 = H // 2
        Sa1 = H * x
        Sb1 = (W - x) * y1
        Sc1 = (W - x) * (H - y1)
        M = max(Sa1,Sb1,Sc1)
        m = min(Sa1,Sb1,Sc1)

        y2 = (W - x) // 2
        Sa2 = H * x
        Sb2 = H * y2
        Sc2 = H * (W - x - y2)
        M2 = max(Sa2,Sb2,Sc2)
        m2 = min(Sa2,Sb2,Sc2)

        if ans > min(M-m,M2-m2):
            ans = min(M-m,M2-m2)

        return ans

if __name__ == '__main__':
    H,W = [int(i) for i in input().split()]
    ans = H * W
    ans = answer(H,W,ans)

    H,W = W,H

    if answer(H,W,ans) < ans:
        ans = answer(H,W,ans)

    print(ans)

Submission status: Wrong Answer

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

for x in range(1,W):
    y1 = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y1
    Sc1 = (W - x) * (H - y1)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    y2 = (W - x) // 2
    Sa2 = H * x
    Sb2 = H * y2
    Sc2 = H * (W - x - y2)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

H,W = W,H
for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    Sa2 = H * x
    Sb2 = H * y
    Sc2 = H * (W - x - y)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)

Submission status: Wrong Answer

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

for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    Sa2 = H * x
    Sb2 = H * y
    Sc2 = H * (W - x - y)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

H,W = W,H
for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    Sa2 = H * x
    Sb2 = H * y
    Sc2 = H * (W - x - y)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)

Submission status: Wrong Answer

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

for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    Sa2 = H * x
    Sb2 = H * y
    Sc2 = H * (W - x - y)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)

Submission status: Wrong Answer

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

for x in range(1,W):
    y = H // 2
    Sa1 = H * x
    Sb1 = (W - x) * y
    Sc1 = (W - x) * (H - y)
    M = max(Sa1,Sb1,Sc1)
    m = min(Sa1,Sb1,Sc1)

    Sa2 = H * x
    Sb2 = H * y
    Sc2 = H * (W - x - y)
    M2 = max(Sa2,Sb2,Sc2)
    m2 = min(Sa2,Sb2,Sc2)

    if ans > min(M-m,M2-m2):
        ans = min(M-m,M2-m2)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w = [int(i) for i in input().split()]
if h % 3 == 0 or w % 3 == 0:
  print(0)

Submission status: Wrong Answer

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

if H > 2:
    HH = H // 3
    S1 = HH * W
    HH = H - H // 3
    HHH = HH // 2
    S2 = HHH * W
    HHH = HH - HH // 2
    S3 = HHH * W
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    HH = H // 3
    S1 = HH * W
    WW = W // 2
    S2 = (H - HH) * WW
    WW = W - W // 2
    S3 = (H - HH) * WW
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    HH = H // 3 + 1
    S1 = HH * W
    WW = W // 2
    S2 = (H - HH) * WW
    WW = W - W // 2
    S3 = (H - HH) * WW
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

if W > 2:
    WW = W // 3
    S1 = WW * H
    WW = W - W // 3
    WWW = WW // 2
    S2 = WWW * H
    WWW = WW - WW // 2
    S3 = WWW * H
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    WW = W // 3
    S1 = WW * H
    HH = H // 2
    S2 = (W - WW) * HH
    HH = H - H // 2
    S3 = (W - WW) * HH
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

    WW = W // 3 + 1
    S1 = WW * H
    HH = H // 2
    S2 = (W - WW) * HH
    HH = H - H // 2
    S3 = (W - WW) * HH
    m = max(S1, S2, S3) - min(S1, S2, S3)
    M = min(M, m)

print(M)

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

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


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

    H, W = il()
    if W % 3 == 0:
        print(0)
    elif H % 3 == 0:
        print(0)
    else:
        ret = MAX
        for h in range(1, H - 1):
            # 横, 横, 横 分割パターン
            hh = (H - h) // 2
            hmin = min(hh * W, (H - h - hh) * W, h * W)
            hmax = max(hh * W, (H - h - hh) * W, h * W)

            # 横, 縦, 縦 分割パターン
            ww = W // 2
            wmin = min((H - h) * (W - ww), (H - h) * ww, h * W)
            wmax = max((H - h) * (W - ww), (H - h) * ww, h * W)

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        for w in range(1, W - 1):
            # 縦, 縦, 縦 分割パターン
            ww = (W - w) // 2
            wmin = min(w * H, (W - w - ww) * H, ww * H)
            wmax = max(w * H, (W - w - ww) * H, ww * H)

            # 縦, 横, 横 分割パターン
            hh = H // 2
            hmin = min(w * H, hh * (W - w), (H - hh) * (W - w))
            hmax = max(w * H, hh * (W - w), (H - hh) * (W - w))

            ret = min(ret, abs(hmax - hmin), abs(wmax - wmin))

        print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W = list(map(int,input().split()))
S = H*W
s1 = 0
ans = 10**10
for i in range(1,H-1):
    s1 += W
    s2 = (H-i)*(W//2)
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    s2 = ((H-i)//2)*W
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

s1 = 0
for i in range(1,W-1):
    s1 += H
    s2 = (W-i)*(H//2)
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

    s2 = ((W-i)//2)*H
    s3 = S - s1 -s2
    ans = min(ans,(max(s1,s2,s3)-min(s1,s2,s3)))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W = list(map(int,input().split()))
target_num = H*W/3
ans = 10**10
H1 = H
W1 = W
#H方向で探す
for i in range( H//3-2, H//3+3):
    s = i*W
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (H-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = i
            W1 = W
        else:
            ans = abs(target_num - s)
            H1 = i
            W1 = W

            
#W方向で探す
for i in range( W//3-2, W//3+3):
    s = i*H
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (W-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        else:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        
#探し終わった。
s1 = H1*W1
nokori = H*W - s1
H = H1 if H == H1 else H-H1
W = W1 if W == W1 else W-W1
#半分にする

target_num = H*W/2
ans = 10**10
H2 = 0
W2 = 0
#H方向で探す
for i in range( H//2-2, H//2+3):
    s = i*W
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = i
        W2 = W
#W方向で探す
for i in range( W//2-2, W//2+3):
    s = i*H
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = H
        W2 = i
#探し終わった。
s2 = H2*W2
nokori = H*W - s2
H = (H-H1)
W = (W-W1)


print(max(s1,s2,nokori)-min(s1,s2,nokori))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W = list(map(int,input().split()))
target_num = H*W/3
ans = 10**10
H1 = H
W1 = W
#H方向で探す
for i in range( H//3-2, H//3+3):
    s = i*W
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (H-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = i
            W1 = W
        else:
            ans = abs(target_num - s)
            H1 = i
            W1 = W

            
#W方向で探す
for i in range( W//3-2, W//3+3):
    s = i*H
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (W-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        else:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        
#探し終わった。
s1 = H1*W1
nokori = H*W - s1
H = H1 if H == H1 else H-H1
W = W1 if W == W1 else W-W1
#半分にする

target_num = H*W/2
ans = 10**10
H2 = 0
W2 = 0
#H方向で探す
for i in range( H//2-1, H//2+2):
    s = i*W
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = i
        W2 = W
#W方向で探す
for i in range( W//2-1, W//2+2):
    s = i*H
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = H
        W2 = i
#探し終わった。
s2 = H2*W2
nokori = H*W - s2
H = (H-H1)
W = (W-W1)


print(max(s1,s2,nokori)-min(s1,s2,nokori))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W = list(map(int,input().split()))
target_num = H*W/3
ans = 10**10
H1 = H
W1 = W
#H方向で探す
for i in range( H//3-1, H//3+2):
    s = i*W
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (H-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = i
            W1 = W
        else:
            ans = abs(target_num - s)
            H1 = i
            W1 = W

            
#W方向で探す
for i in range( W//3-1, W//3+2):
    s = i*H
    if abs(target_num - s) <= ans:
        if abs(target_num - s) == ans and (W-i)%2 == 0:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        else:
            ans = abs(target_num - s)
            H1 = H
            W1 = i
        
#探し終わった。
s1 = H1*W1
nokori = H*W - s1
H = H1 if H == H1 else H-H1
W = W1 if W == W1 else W-W1
#半分にする

target_num = H*W/2
ans = 10**10
H2 = 0
W2 = 0
#H方向で探す
for i in range( H//2-1, H//2+2):
    s = i*W
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = i
        W2 = W
#W方向で探す
for i in range( W//2-1, W//2+2):
    s = i*H
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = H
        W2 = i
#探し終わった。
s2 = H2*W2
nokori = H*W - s2
H = (H-H1)
W = (W-W1)


print(max(s1,s2,nokori)-min(s1,s2,nokori))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W = list(map(int,input().split()))
target_num = H*W/3
ans = 10**10
H1 = 0
W1 = 0
#H方向で探す
for i in range( H//3-1, H//3+2):
    s = i*W
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H1 = i
        W1 = W
#W方向で探す
for i in range( W//3-1, W//3+2):
    s = i*H
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H1 = H
        W1 = i
#探し終わった。
s1 = H1*W1
nokori = H*W - s1
H = H1 if H == H1 else H-H1
W = W1 if W == W1 else W-W1
#半分にする

target_num = H*W/2
ans = 10**10
H2 = 0
W2 = 0
#H方向で探す
for i in range( H//2-1, H//2+2):
    s = i*W
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = i
        W2 = W
#W方向で探す
for i in range( W//2-1, W//2+2):
    s = i*H
    if abs(target_num - s) < ans:
        ans = abs(target_num - s)
        H2 = H
        W2 = i
#探し終わった。
s2 = H2*W2
nokori = H*W - s2
H = (H-H1)
W = (W-W1)


print(max(s1,s2,nokori)-min(s1,s2,nokori))

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
stand=h*w/3
prevh,prevw=1,1
mini=10**18
for i in range(2,h+1):
    if abs(stand-i*w)<abs(stand-prevh*w):
        prevh=i
if h-prevh>=2:
    mini=min(mini,max((h-prevh)//2*w,prevh*w,-(-(h-prevh)//2)*w)-min((h-prevh)//2*w,prevh*w,-(-(h-prevh)//2)*w))
mini=min(mini,max(w//2*(h-prevh),prevh*w,-(-w//2)*(h-prevh))-min(w//2*(h-prevh),prevh*w,-(-w//2)*(h-prevh)))
#print(mini)
for i in range(2,w+1):
    if abs(stand-i*h)<abs(stand-prevw*h):
        prevw=i
if w-i>=2:
    mini=min(mini,max((w-prevw)//2*h,prevw*h,-(-(w-prevw)//2)*h)-min((w-prevw)//2*h,prevw*h,-(-(w-prevw)//2)*h))
mini=min(mini,max(h//2*(w-prevw),prevw*h,-(-h//2)*(w-prevw))-min(h//2*(w-prevw),prevw*h,-(-h//2)*(w-prevw)))
print(mini)

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, 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):
    p1 = a//3 * b
    left_1 = H*W - p1
    p2 = b//2 * (a - a//3)
    p3 = left_1 - p2
    diff_1 = max(p1, p2, p3) - min(p1, p2, p3)

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

    return min(diff_1, diff_2)

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
tanpen = min(h, w)
chohen = max(h, w)

if h%3 == 0 or w%3 == 0:
    print(0)
else:
    s, r = divmod(h*w, 3)

    ans = h*w
    for i in range(1, chohen):
        s1 = i*tanpen
        s2 = (tanpen//2) * (chohen - i)
        s3 = (tanpen - tanpen//2) * (chohen - i)
        ans = min(ans, max(s1, s2, s3) - min(s1, s2, s3))
    print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
H, W = LI()


def main():
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return
    a = max(H, W)
    b = min(H, W)
    x = a // 3
    if a % 3 == 2:
        x += 1
    n1 = b * x
    a -= x
    if a < b:
        a, b = b, a
    if a % 2 == 0 or b % 2 == 0:
        n2 = n3 = (a * b) // 2
    else:
        y = a // 2
        n2 = b * y
        n3 = b * (a - y)
    ans = max(n1, n2, n3) - min(n1, n2, n3)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
if (h%3==0 or w%3==0):
    print(0)
    exit()
ans = float("inf")
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    if (h%3==1):
        ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    else:
        ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
    
a = w
w = h
h = a
#print(h,w)
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    if (h%3==1):
        ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    else:
        ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
    
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()
ans = float("inf")
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
#else:
#    ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
#    ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
#print(ans)
    
a = w
w = h
h = a
#print(h,w)
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
    
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()
ans = float("inf")
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
#print(ans)
    
a = w
w = h
h = a
#print(h,w)
if (w%2==0):
    ans = min(ans, (h-h//3)*(w//2) - h//3*w)
    ans = min(ans, abs((h-h//3-1)*(w//2) - (h//3+1)*w))
else:
    ans = min(ans, max(abs((h-h//3)*(w//2) - h//3*w),abs((h-h//3)*(w//2+1) - h//3*w), abs(h-h//3)))
    ans = min(ans, max(abs((h-h//3-1)*(w//2) - (h//3+1)*w),abs((h-h//3-1)*(w//2+1) - (h//3+1)*w), abs(h-h//3-1)))
    
print(ans)