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 max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h

        tmp = solve2(h, w - w2)
        tmp = max_minus_min(tmp)
        # ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])

        tmp = solve2(w - w2, h)
        # ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Wrong Answer

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h

        tmp = solve2(h, w - w2)
        # ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])

        tmp = solve2(w - w2, h)
        # ans = min(ans, max_minus_min([area1, tmp[0], tmp[1]])
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Wrong Answer

Solution code:
def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return area1, area2
 
def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    # for w2 in range(w_div_3, w_div_3 + 2):
    #     area1 = w2 * h
    #     ans = min(ans, max_minus_min([area1, *solve2(h, w - w2)]))
    #     ans = min(ans, max_minus_min([area1, *solve2(w - w2, h)]))
    return ans
 
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Wrong Answer

Solution code:
h,w=map(int,raw_input().split())
if h>w:w,h=h,w
if h%3==0 or w%3==0:
    print 0
else:
    if w%3==2:
        print abs((w/3+1)*h-(w-(w/3+1))*(h/2))
    else:
        print (h+1)/2

Submission status: Wrong Answer

Solution code:
import math as mt

w,h = [int(x) for x in input().split()]
if w % 3 == 0 or h % 3 == 0:
    print(0)
else:
    coll = [0,0,0,0]
    for index,(a,b) in enumerate([(w,h),(h,w)]):
        if a % 2 == 0:
            k = a/2
            x = 3 - b%3
            coll[index] = k * x
            x = b % 3
            if k * x < coll[index]:
                coll[index] = k
        else:
            k = (a-1)/2
            coll[index] = 3*k+1 - (k*b) % (3*k+1)
            if (k*b + b) % (3*k+2) < coll[index]:
                coll[index] = (k*b + b) % (3*k+2)
            j =  b - mt.floor(b/3)
            if j < coll[index] and k * j < mt.floor(b/3) * a:
                coll[index] = j
    coll[2] = a
    coll[3] = b
    print(int(min(coll)))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_d(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        rng = range(x) if x < 1000 else range(x//3, x*4//5)
        for i in rng:
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            smax = max(s2, s2)
            new_d = max(abs(s1-smax), abs(s1-smax))
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    d1 = calculate_d(h, w)
    if h == w:
        print(d1)
    else:
        d2 = calculate_d(w, h)
        print(min(d1,d2))

Submission status: Wrong Answer

Solution code:

import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b
    if a%3==0 or b%3==0:
        return 0

    if fc=="ceil":
        x=math.ceil((S/3)/a)
    else:
        x=math.floor((S/3)/a)
    l=math.floor(a/2)
    S_l=(b-x)*l
    S_U=a*x
    S_r=(b-x)*(a-l)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return abs(SMax-SMin)

def solve3(a,b):
    la=a//3
    lb=a//3
    lc=a-(la+lb)

    Sa=la*b
    Sb=lc*b
    return abs(Sa-Sb)




s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")
s5=solve3(a,b)
s6=solve3(b,a)
print(min(s1,s2,s3,s4,s5,s6))

Submission status: Wrong Answer

Solution code:

import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b
    if a%3==0 or b%3==0:
        return 0
        
    if fc=="ceil":
        x=math.ceil((S/3)/a)
    else:
        x=math.floor((S/3)/a)
    l=math.floor(a/2)
    S_l=(b-x)*l
    S_U=a*x
    S_r=(b-x)*(a-l)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return abs(SMax-SMin)



s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")
print(min(s1,s2,s3,s4))

Submission status: Wrong Answer

Solution code:
import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b

    if fc=="ceil":
        x=math.ceil((S/3)/a)
    else:
        x=math.floor((S/3)/a)
    l=math.floor(a/2)
    S_l=(b-x)*l
    S_U=a*x
    S_r=(b-x)*(a-l)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return abs(SMax-SMin)



s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")
print(min(s1,s2,s3,s4))

Submission status: Wrong Answer

Solution code:
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=100000000
ans=INF
#超特殊例
if H==1 or W==1:
	ans=1
if H%3==0 or W%3==0:
	ans=0
#横長がある場合
for i in range(H):
	S1=W*i
	S2=int(W/2)*(H-i)
	S3=(W-int(W/2))*(H-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
for i in range(W):
	S1=H*i
	S2=int(H/2)*(W-i)
	S3=(H-int(H/2))*(W-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b

    if fc=="floor":
        x=math.ceil((S//3)/a)
    else:
        x=math.floor((S//3)/a)
    S_l=(b-x)*math.floor(a/2)
    S_U=a*x
    S_r=(b-x)*math.ceil(a/2)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return SMax-SMin



s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_d(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        rng = range(x) if x < 1000 else range(x//3, x*4//5)
        for i in rng:
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            new_d = max(abs(s1-s2), abs(s1-s3))
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    d1 = calculate_d(h, w)
    d2 = calculate_d(w, h)
    print(min(d1,d2))

Submission status: Wrong Answer

Solution code:
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=100000000
ans=INF
if H%3==0 or W%3==0:
	ans=0
#横長がある場合
for i in range(H):
	S1=W*i
	S2=int(W/2)*(H-i)
	S3=(W-int(W/2))*(H-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
for i in range(W):
	S1=H*i
	S2=int(H/2)*(W-i)
	S3=(H-int(H/2))*(W-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
	
print(ans)

Submission status: Wrong Answer

Solution code:

import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b

    if fc=="floor":
        x=math.ceil((S//3)/a)
    else:
        x=math.floor((S//3)/a)
    S_l=(b-x)*math.floor(a/2)
    S_U=a*x
    S_r=(b-x)*math.ceil(a/2)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return SMax-SMin



sa=solve(a,b,"floor")
sb=solve(b,a,"ceil")
print(min(sa,sb))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
if h%3 == 0 or w%3 ==0:
    print(0)
else:
    def calculate_d(x, y):
        d = h*w + 1
        i = x//2
        s1, s2 = 0, d
        for i in range(x):
            s1 = (y//2)*i
            s2 = y*(x-i)
            s3 = (y-y//2)*i
            new_d = max(abs(s1-s2), abs(s1-s3))
            if d > new_d:
                d = new_d
                continue
            else:
                break
        return d
    d1 = calculate_d(h, w)
    d2 = calculate_d(w, h)
    print(min(d1,d2))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    H, W = ILI()
    return (H, W)

def solve(H, W):
    if H % 3 == 0 or W % 3 == 0:
        return 0

    ans = INF
    
    if W % 2 == 0:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * W // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * (W // 2)
            num_3 = (H - h) * (W // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))
    
    if H % 2 == 0:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * H // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for w in range(1, W):
            num_1 = w * H
            num_2 = (W - w) * (H // 2)
            num_3 = (W - w) * (H // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))
    
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
h, w = [int(i) for i in input().split()]
h3 = int(h/3)
w3 = int (w/3)
ret = sys.maxsize
# ||| Split
if(h % 3 == 0 or w % 3 == 0):
    ret = 0
a1 = h3 * w
a2 = (h3+1) * w
if(ret > a2 - a1):
    ret = a2 - a1
a1 = w3 * h
a2 = (w3+1) * h
if(ret > a2 - a1):
    ret = a2 - a1
# print("|||:", a2 - a1)

# T Split
a1 = h3 * w
a2 = (h-h3) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h3)
a3 = (h-h3) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin

# print("T1: ", amax - amin)

h31 = h3 + 1
a1 = (h31) * w      # 10
a2 = (h-h31) * int(w/2)  # 6
if(w % 2 == 1):
    a2 += (h-h31) # 9
a3 = (h-h31) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin

# print("T2: ", amax - amin, amax, amin)

h, w = w, h
a1 = h3 * w
a2 = (h-h3) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h3)
a3 = (h-h3) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin

# print("T3: ", amax - amin)

h31 = h3 + 1
a1 = (h31) * w
a2 = (h-h31) * int(w/2)
if(w % 2 == 1):
    a2 += (h-h31)
a3 = (h-h31) * int(w/2)
amin = a1
if(a1 > a3):
    amin = a3
amax = a2
if(a1 > a2):
    amax = a1
if(ret > (amax - amin)):
    ret = amax - amin

# print("T4: ", amax - amin)

print(int(ret))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    H, W = ILI()
    return (H, W)

def solve(H, W):
    if H % 3 == 0 or W % 3 == 0:
        return 0

    ans = INF

    if W % 2 == 0:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * W // 2
            ans = min(ans, abs(num_1 - num_2))
    else:
        for h in range(1, H):
            num_1 = h * W
            num_2 = (H - h) * (W // 2)
            num_3 = (H - h) * (W // 2 + 1)
            nums = sorted([num_1, num_2, num_3])
            ans = min(ans, (nums[2] - nums[0]))

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def score(s, t, u):
    return max([s, t, u]) - min([s, t, u])


def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    res = w * h
    for i in range(1, h - 1):
        s = i * w
        if (h - i) % 2 == 0 or w % 2 == 0:
            t = u = (h - i) * w // 2
            r = score(s, t, u)
            if res > r:
                res = r
        else:
            t = (h - i) // 2 * w
            u = ((h - i) // 2 + 1) * w
            r = score(s, t, u)
            if res > r:
                res = r
            t = w // 2 * (h - i)
            u = (w // 2 + 1) * (h - i)
            r = score(s, t, u)
            if res > r:
                res = r
    return res

# import sys
# sys.stdin = open('a1.in')
h, w = map(int, input().split())
res = min(solve(w, h), solve(h, w))
print(res)

Submission status: Wrong Answer

Solution code:
import math as mt

w,h = [int(x) for x in input().split()]
if w % 3 == 0 or h % 3 == 0:
    print(0)
else:
    coll = [0,0,0,0]
    for index,(a,b) in enumerate([(w,h),(h,w)]):
        if a%2 == 0:
            k = a/2
            x = 3 - b%3
            coll[index] = k * x
            x = b%3
            if k * x < coll[index]:
                coll[index] = k
        else:
            k = (a-1)/2
            coll[index] = 3*k+1 - (k*b) % (3*k+1)
            if (k*b + b) % (3*k+2) < coll[index]:
                coll[index] = (k*b + b) % (3*k+2)
    coll[2] = a
    coll[3] = b
    print(int(min(coll)))

Submission status: Wrong Answer

Solution code:
import math as mt

w,h = [int(x) for x in input().split()]
if w % 3 == 0 or h % 3 == 0:
    print(0)
else:
    coll = [0,0,0,0]
    for index,(a,b) in enumerate([(w,h),(h,w)]):
        if a%2 == 0:
            k = a/2
            x = 3 - b%3
            coll[index] = k * x
            x = b%3
            if k * x < coll[index]:
                coll[index] = k
        else:
            k = (a-1)/2
            coll[index] = 3*k+1 - (k*b) % (3*k+1)
            if (k*b + b) % (3*k+2) < coll[index]:
                coll[index] = (k*b + b) % (3*k+2)
    coll[2] = a
    coll[3] = b
    print(min(coll))

Submission status: Wrong Answer

Solution code:
def score(s, t, u):
    return max([s, t, u]) - min([s, t, u])


def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    res = w * h
    for i in range(1, h - 1):
        s = i * w
        if (h - i) % 2 == 0 or w % 2 == 0:
            t = u = (h - 1) * w / 2
            r = score(s, t, u)
            if res > r:
                res = r
        else:
            t = (h - i) // 2 * w
            u = ((h - i) // 2 + 1) * w
            r = score(s, t, u)
            if res > r:
                res = r
            t = w // 2 * (h - i)
            u = (w // 2 + 1) * (h - i)
            r = score(s, t, u)
            if res > r:
                res = r
    return res


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

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return

    def c(H, W):
        HW = H * W
        ans = HW
        for i in range(1, H):
            I = i * W
            O = (H - i) // 2 * W
            G = HW - I - O
            ans = min(ans, max(abs(I - O), abs(G - O)))
    
        for i in range(1, H):
            I = i * W
            O = (H - i) * (W // 2)
            G = HW - I - O
            ans = min(ans, max(abs(I - O), abs(G - O)))
        return ans
    
    print(min(c(H, W), c(W, H)))

main()

Submission status: Wrong Answer

Solution code:
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=100000000

ans=INF

if H%3==0 or W%3==0:
	print(0)
if H%2==0:
	for i in range(W):
		S1=H*i
		S2=int(H/2)*(W-i)
		if abs(S1-S2)<ans:
			ans=abs(S1-S2)
if W%2==0:
	ans=INF
	for i in range(H):
		S1=W*i
		S2=int(W/2)*(H-i)
		if abs(S1-S2)<ans:
			ans=min(ans,abs(S1-S2))
			
for i in range(H):
	for j in range(W):
		#横長がある場合
		S1=W*i
		S2=j*(H-i)
		S3=(W-j)*(H-i)
		minS=min(S1,S2,S3)
		maxS=max(S1,S2,S3)
		if maxS-minS<ans:
			ans=maxS-minS
		#縦長がある場合
		S1=H*j
		S2=i*(W-j)
		S3=(H-i)*(W-j)
		minS=min(S1,S2,S3)
		maxS=max(S1,S2,S3)
		if maxS-minS<ans:
			ans=maxS-minS
#縦or横三分割する場合
ans=min(ans,H,W)

	
	
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return

    def c(H, W):
        HW = H * W
        ans = HW
        for i in range(1, H):
            I = i * W
            O = (H - i) // 2 * W
            G = HW - I - O
    
        for i in range(1, H):
            I = i * W
            O = (H - i) * (W // 2)
            G = HW - I - O
            ans = min(ans, max(abs(I - O), abs(G - O)))
        return ans
    
    print(min(c(H, W), c(W, H)))

main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return
    
    ans = H * W

    for i in range(1, H):
        I = i * W
        O = (H - i) * (W // 2)
        G = (H - i) * W - O
        ans = min(ans, max(abs(I - O), abs(G - O)))
        
    H, W = W, H
    
    for i in range(1, H):
        I = i * W
        O = (H - i) * (W // 2)
        G = (H - i) * W - O
        ans = min(ans, max(abs(I - O), abs(G - O)))
    
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    
    if H % 3 == 0 or W % 3 == 0:
        print(0)
        return
    
    ans = H * W

    for i in range(1, H - 1):
        I = i * W
        O = (H - i) * (W // 2)
        G = (H - i) * W - O
        ans = min(ans, max(abs(I - O), abs(G - O)))
        
    H, W = W, H
    
    for i in range(1, H - 1):
        I = i * W
        O = (H - i) * (W // 2)
        G = (H - i) * W - O
        ans = min(ans, max(abs(I - O), abs(G - O)))
    
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def solve(h, w):
    if h % 3 == 0 or w % 3 == 0:
        return 0
    min_diff = h * w
    vals = [0, 0, 0]
    for i in range(1, w // 2 + 1):
        vals[0] = i * h
        if h % 2 == 0:
            vals[1] = (w - i) * (h // 2)
            vals[2] = vals[1]
        else:
            vals[1] = (w - i) * (h // 2 + 1)
            vals[2] = (w - i) * (h // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
        if (w - i) % 2 == 0:
            vals[1] = h * ((w - i) // 2)
            vals[2] = vals[1]
        else:
            vals[1] = h * ((w - i) // 2 + 1)
            vals[2] = h * ((w - i) // 2)
        diff = max(vals) - min(vals)
        if diff < min_diff:
            min_diff = diff
        h, w = w, h
        for i in range(1, w // 2 + 1):
            vals[0] = i * h
            if h % 2 == 0:
                vals[1] = (w - i) * (h // 2)
                vals[2] = vals[1]
            else:
                vals[1] = (w - i) * (h // 2 + 1)
                vals[2] = (w - i) * (h // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
            if (w - i) % 2 == 0:
                vals[1] = h * ((w - i) // 2)
                vals[2] = vals[1]
            else:
                vals[1] = h * ((w - i) // 2 + 1)
                vals[2] = h * ((w - i) // 2)
            diff = max(vals) - min(vals)
            if diff < min_diff:
                min_diff = diff
    return min_diff

_h, _w = map(int, input().split())
print(solve(_h, _w))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
if H%3 == 0 or W%3 == 0:
    print(0)
else:
    MIN = 10**10
    horizon = min(H,W)
    h = int((H-1)/2)+1
    w = int((W-1)/2)+1
    for i in range(h):
        j = 0
        for j in range(w):
            tile = [0,0,0,0]
            tile[0] = (i+1)*(j+1)
            tile[1] = (i+1)*(W-(j+1))
            tile[2] = (H-(i+1))*(j+1)
            tile[3] = (H-(i+1))*(W-(j+1))
            tile.sort()
            Next = tile.pop(1)
            tile[0] = tile[0]+Next
            kari = (max(tile)-min(tile))
            if MIN >= kari:
                MIN = kari
    print(min(horizon,MIN))

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    #縦3分割
    h1 = h//3
    h2 = (h-h1)//2
    h3 = h-h1-h2
    ans = (max(h1,h2,h3)-min(h1,h2,h3))*w
    #横3分割
    w1 = w//3
    w2 = (w-w1)//2
    w3 = w-w1-w2
    a = (max(w1,w2,w3)-min(w1,w2,w3))*h
    if a<ans:
        ans = a
    #縦1横２分割
    h1 = h//3
    h2 = h-h1
    w1 = w//2
    w2 = w-w1
    a = max(h1*w,h2*w1,h2*w2)-min(h1*w,h2*w1,h2*w2)
    if a<ans:
        ans = a
    h1 = h//3+1
    h2 = h-h1
    w1 = w//2
    w2 = w-w1
    a = max(h1*w,h2*w1,h2*w2)-min(h1*w,h2*w1,h2*w2)
    if a<ans:
        ans = a
    #縦2横1分割
    w1 = w//3
    w2 = w-w1
    h1 = h//2
    h2 = h-h1
    a = max(w1*h,w2*h1,w2*h2)-min(w1*h,w2*h1,w2*h2)
    if a<ans:
        ans = a
    w1 = w//3+1
    w2 = w-w1
    h1 = h//2
    h2 = h-h1
    a = max(w1*h,w2*h1,w2*h2)-min(w1*h,w2*h1,w2*h2)
    if a<ans:
        ans = a
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ans = float("inf")
for i in range(1,h+1):
    if w % 2 == 1 and (h-i) % 2 == 1:
        ans = min(ans, max(w*i, (h-i)*(w//2), (h-i)*(w//2+1))-min(w*i, (h-i)*(w//2), (h-i)*(w//2+1)))
    elif (h-i) % 2 == 0:
        ans = min(ans, max(w*i, (h-i)//2*w)-min(w*i, (h-i)//2*w))
    else:
        ans = min(ans, max(w*i, (h-i)*(w//2))-min(w*i, (h-i)*(w//2)))
h, w = w, h
for i in range(1,h+1):
    if w % 2 == 1 and (h-i) % 2 == 1:
        ans = min(ans, max(w*i, (h-i)*(w//2), (h-i)*(w//2+1))-min(w*i, (h-i)*(w//2), (h-i)*(w//2+1)))
    elif (h-i) % 2 == 0:
        ans = min(ans, max(w*i, (h-i)//2*w)-min(w*i, (h-i)//2*w))
    else:
        ans = min(ans, max(w*i, (h-i)*(w//2))-min(w*i, (h-i)*(w//2)))
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
def func(a,b):
  ret = []
  for h1 in (a//3,a//3+1):
    a1 = h1*b
    nh = a-h1
    c = (a1,nh//2*b,(nh-nh//2)*b)
    ret.append(max(c)-min(c))
    c = (a1,nh*(b//2),nh*(b-b//2))
    ret.append(max(c)-min(c))
  return min(ret)
print(min(func(h,w),func(w,h)))

Submission status: Accepted

Solution code:
def calc(h, w):
  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)])
  return ans
def main():
  a, b = map(int,  input().split())
  print(min([calc(a,  b), calc(b, a)]))
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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):
            _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: Accepted

Solution code:
H,W = map(int,input().split())
def HW(H,W):
    if H%2 == 0 or W%2 == 0:
        return [H*W//2]*2
    else:
        A = min((H+1)//2*W-(H-1)//2*W,(W+1)//2*H-(W-1)//2*H)
        if A == (H+1)//2*W-(H-1)/2*W:
            return [(H+1)//2*W,(H-1)//2*W]
        else:
            return [(W+1)//2*H,(W-1)//2*H]
Ans = H*W
for i in range(1,H):
    A1 = W*i
    S = HW(H-i,W)
    S.append(A1)
    Ans = min(Ans,abs(max(S)-min(S)))
for j in range(1,W):
    A1 = H*j
    S = HW(H,W-j)
    S.append(A1)
    Ans = min(Ans,abs(max(S)-min(S)))
print(Ans)

Submission status: Accepted

Solution code:
def solve(H,W):
    p1 = [H//3*W, (H-H//3)*(W//2), (H-H//3)*(W-W//2)]
    p2 = [ceil(H/3)*W, (H-ceil(H/3))*(W//2), (H-ceil(H/3))*(W-W//2)]
    S1 = max(p1)-min(p1)
    S2 = max(p2)-min(p2)
    S3 = 0 if H%3==0 else W
    return min(S1,S2,S3)

from math import ceil
H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))

Submission status: Accepted

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

"""
1. 1回目の割れ目をタテヨコ1かいどこかにいれる。
2. 残りは2つに別れたチョコの面積大きい方を極力2分割する。
   その時、両辺とも奇数の場合は、最小でも短辺分の長さの差が生まれる。
2の操作はO(1)で実施できるため、O(n)で実行可能であるから、
この問題に対して十分高速である。
"""

def split_choco(h, w):
    if h > w:
        h, w = w, h
    if h*w%2 == 0:
        return h*w//2, h*w//2
    else:
        assert w%2==1
        w1 = w//2
        w2 = w//2+1
        return h*w2, h*w1

# まずヨコ方向に割る
ans = float('inf')
for i in range(1, H//2+1):
    large = (H-i, W)
    choco = [i*W] + list(split_choco(*large))
    ans = min(ans, max(choco)-min(choco))
# まずタテに割る
for i in range(1, W//2+1):
    large = (H, W-i)
    choco = [i*H] + list(split_choco(*large))
    ans = min(ans, max(choco)-min(choco))
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int,input().split())
    area = H * W
    ans = 10**10
    # 縦に3分割
    for i in range(W//3,W//3+2):
        for j in range(W//3,W//3+2):
            areas = [H*i,H*(W-j-i),H*j]
            ans = min(ans,max(areas)-min(areas))
    # 横に3分割
    for i in range(H//3, H//3+2):
        for j in range(H//3,H//3+2):
            areas = [W*i, W*(H-i-j), W*j]
            ans = min(ans, max(areas)-min(areas))
    
    # 縦に大きく分割したあと横に分割
    for i in range(W//3,W//3+2):
        areas = [H*i]
        w_remain = W - i
        for j in range(H//2,H//2+2):
            h_remain = H - j 
            areas.append(w_remain * j)
            areas.append(w_remain * h_remain)
            ans = min(ans, max(areas)-min(areas))
    
    # 横に大きく分割したあと縦に分割
    for i in range(H//3,H//3+1):
        areas = [W*i]
        h_remain = H - i
        for j in range(W//2, W//2+2):
            w_remain = W - j
            areas.append(h_remain * j)
            areas.append(h_remain * w_remain)
            ans = min(ans, max(areas)-min(areas))


    print(ans)

main()

Submission status: Accepted

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):
        M=max(hi*w,(h-hi)*((w+1)//2),(h-hi)*(w//2))
        m=min(hi*w,(h-hi)*((w+1)//2),(h-hi)*(w//2))
        ans=min(ans,M-m)
    for wi in range(1,w):
        M=max(wi*h,(w-wi)*((h+1)//2),(w-wi)*(h//2))
        m=min(wi*h,(w-wi)*((h+1)//2),(w-wi)*(h//2))        
        ans=min(ans,M-m)
    print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    ans = float('inf')
    h1, h2, h3 = 0,0,0
    w1,w2,w1 = 0,0,0
    # 横3に切る場合
    h1 = H // 3
    h2 = H // 3
    h3 = H // 3
    if H % 3 == 1:
        h3 += 1
    elif H % 3 == 2:
        h2 += 1
        h3 += 1
    S = [h1*W,h2*W,h3*W]
    ans = min(max(S)-min(S),ans)
    # 横2縦1に切る場合
    h1 = H // 2
    h2 = H // 2
    h3 = H
    if H % 2 == 1:
        h2 += 1
    for w in range(1,W):
        S = [h1*(W-w),h2*(W-w),h3*w]
        ans = min(max(S)-min(S),ans)
    # 縦3に切る場合
    w1 = W // 3
    w2 = W // 3
    w3 = W // 3
    if W % 3 == 1:
        w3 += 1
    elif W % 3 == 2:
        w2 += 1
        w3 += 1
    S = [w1*H,w2*H,w3*H]
    ans = min(max(S)-min(S),ans)

    # 縦1横2に切る場合
    w1 = W // 2
    w2 = W // 2
    w3 = W
    if W % 2 == 1:
        w2 += 1
    for h in range(1,H):
        S = [w1*(H-h),w2*(H-h),w3*h]
        ans = min(max(S)-min(S),ans)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def get_min(h, w):
    res = float("inf")
    for i in range(1, h):
        up = [w // 2 * i, (w - w // 2) * i, w * (h - i)]
        res = min(res, max(up) - min(up))
        down = [w * i, w // 2 * (h - i), w - (w - w // 2) * (h - i)]
        res = min(res, max(down) - min(down))
    return res


H, W = map(int, input().split())
if H % 3 == 0 or W % 3 == 0:
    print(0)
    exit()

ans = min(H, W)
ans = min(ans, get_min(H, W))
ans = min(ans, get_min(W, H))
print(ans)

Submission status: Accepted

Solution code:
import sys

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

ans=10**10

S=[]

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


for h1 in [h//3,(h//3)+1]:
  if ((h-h1)*w)%2==0:
    S.append([h1*w,((h-h1)*w)//2,((h-h1)*w)//2])
  else:
    S.append([h1*w,((h-h1)//2)*w,((h-h1)//2+1)*w])
    S.append([h1*w,(w//2)*(h-h1),(w//2+1)*(h-h1)])

for w1 in [w//3,(w//3)+1]:
  if ((w-w1)*h)%2==0:
    S.append([w1*h,((w-w1)*h)//2,((w-w1)*h)//2])
  else:
    S.append([w1*h,((w-w1)//2)*h,((w-w1)//2+1)*h])
    S.append([w1*h,(h//2)*(w-w1),(h//2+1)*(w-w1)])

for si in S:
  ans=min(ans,max(si)-min(si))

print(ans)