125AC - ABC063C: Chocolate Bar

競プロ
ABC063-C (400 points)
問題

縦 H ブロック, 横 W ブロックの板チョコをブロックに沿った長方形に三分割するとき, 最も大きいピースの面積 S_{max} と最も小さいピースの面積 S_{min} の差 S_{max} - S_{min} の最小値を求める.

  • 2 \leq H, W \leq 10^5
方針
  • ↓の4つの分割について考えれば十分.

f:id:tpnbnk:20180627132748p:plain

  • 四番目の分割方法について考える. ただし B \leq C とし, A の幅を i とする.
  • B と C はできるだけ等しくすべきであることは容易に証明可能（そうでなければ, より均等に近づけることで S_{max} - S_{min} を改善可能）.
  • よって, B の高さ = \lfloor \frac{H}{2} \rfloor, C の高さ = \lceil \frac{H}{2} \rceil .
  • このとき, A の部分は必ず S_{max} か S_{min} になるので, それぞれの場合のギリギリの i を求める.
import math

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

# 同じ方向に三等分
ans0 = (W % 3 != 0) * H
ans1 = W * (H % 3 != 0)

# T字分割
blue_H = math.floor(H / 2)
i = math.floor((W * blue_H) / (H + blue_H))
ans2 = math.ceil(H / 2) * (W - i) - H * i

red_H = math.ceil(H / 2)
i = math.ceil((W * red_H) / (H + red_H))
ans3 = H * i - math.floor(H / 2) * (W - i)

blue_W = math.floor(W / 2)
i = math.floor((H * blue_W) / (W + blue_W))
ans4 = math.ceil(W / 2) * (H - i) - W * i

red_W = math.ceil(W / 2)
i = math.ceil((H * red_W) / (W + red_W))
ans5 = W * i - math.floor(W / 2) * (H - i)

ans = min(ans0, ans1, ans2, ans3, ans4, ans5)

print(ans)