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: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

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: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))
B = []
for i in range(n,2*n + 1):
	A1 = A[:i]
	A2 = A[i:]
	a1 = i - n
	a2 = 2 * n - i
	A1.sort()
	A1 = A1[a1:]
	A2.sort()
	if a2 != 0:
		A2 = A2[:-a2]
	#print(A1,A2)
	B.append(sum(A1) - sum(A2))
#print(B)
print(max(B))

Submission status: Runtime Error

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: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <climits>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::memset;
using std::memset;
using std::floor;
using std::abs;
using std::min;
using std::max;

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    long h, w;
    cin >> h >> w;
    if (h % 3 == 0 || w % 3 == 0)
    {
        cout << 0;
        return 0;
    }
    if (h > w){
        long tmp = w;
        w = h;
        h = tmp;
    }
    
    //口日
    long diff = h ;
    long d;
    long s[3] = {};
    for (int x = 0; x <= w; ++x)
    {
        s[0] = x * h;
        s[1] = (w - x) * floor(h / 2);
        s[2] = h * w - s[0] - s[1];
        d = max(abs(s[0] - s[1]), min(abs(s[1] - s[2]), abs(s[0] - s[2])));
        diff = min(d,diff);
        if(diff == 0)break;
    }
    for (int x = 0; x <= h; ++x)
    {
        s[0] = x * w;
        s[1] = (h - x) * floor(w / 2);
        s[2] = h * w - s[0] - s[1];
        d = max(abs(s[0] - s[1]), min(abs(s[1] - s[2]), abs(s[0] - s[2])));
        diff = min(d,diff);
        if(diff==0)break;
    }
    cout << diff;
    return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

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