#K93557. Maximizing Trees in a Garden
Maximizing Trees in a Garden
Maximizing Trees in a Garden
You are given a garden with m rows and n columns. You need to plant as many trees as possible under the following conditions:
- No two trees are planted in the same row or column.
- The Manhattan distance between any two trees is at least 2. That is, for any two trees at positions \((i_1, j_1)\) and \((i_2, j_2)\), the condition
\(|i_1 - i_2| + |j_1 - j_2| \ge 2\) must hold.
It can be shown that the maximum number of trees that can be planted is given by the formula:
$$\left\lfloor \frac{m+1}{2} \right\rfloor \times \left\lfloor \frac{n+1}{2} \right\rfloor$$
Your task is to compute this value given m and n.
inputFormat
The input consists of two space-separated integers m
and n
on a single line.
outputFormat
Output a single integer representing the maximum number of trees that can be planted in the garden.
## sample4 4
4