Problem: 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}.

Submission attempts (in order):
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, tmp)

        tmp = solve2(w - w2, h)
        tmp = max_minus_min(tmp)
        ans = min(ans, tmp)


def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)
 
def solve2(h, w):
    return 7, 7
    # 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)))


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


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


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)


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


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


def max_minus_min(areas):
    # print("areas", areas)
    # return max(areas) - min(areas)
    return 999
 
def solve2(h, w):
    return 7, 7
    # 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 = max_minus_min([area1] + solve2(h, w - w2))

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


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


def max_minus_min(areas):
    # print("areas", areas)
    # return max(areas) - min(areas)
    return 999
 
def solve2(h, w):
    return 7, 7
    # 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)))


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


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Accepted