コンテンツにスキップ

SamCoding Round 7 (Div. 2) E - Park Lamps

サイト
SamCoding
コンテスト
SamCoding Round 7 (Div. 2)
問題
E - Park Lamps(常設版)

n×mn \times m のマス目があり、マスの境界(長さ 11 の道)の中央にランプを置けます。ランプはその道を挟む 22 マスを照らします(外周の道なら 11 マスだけ)。すべてのマスを照らすのに必要なランプの最小個数を求める問題です(1≤n,m≤1051 \le n, m \le 10^5)。

答えは ⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil です。

  • これより少なくはできない: ランプ 1 個で照らせるのは高々 22 マスなので、nmnm マスを照らすには nm2\frac{nm}{2} 個以上必要です。
  • この個数で照らせる: マス目は、隣り合う 22 マスの組(ドミノ)で、高々 11 マスを残して敷き詰められます。たとえば各行を左から 22 マスずつ組にし、各行の余りは縦に 22 マスずつ組にします。各ドミノの間の道にランプを置き、残った 11 マスがあればその周りの道に 11 個置けば、⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil 個ですべてのマスを照らせます。
Python
N, M = map(int, input().split())
print((N * M + 1) // 2)

(N * M + 1) // 2 で nm2\frac{nm}{2} の切り上げを計算しています。