Walimah
Time limit: 1 s.
Memory limit: 256 MB
In a hall prepared for a Walimah, each square meter of floor can contain either one square table or one chair. Around each square table, at most 8 chairs can be placed: one along each side and one at each corner.
Write a program that calculates the maximum possible number of chairs that can be placed in the hall, assuming that every chair must be placed next to at least one table.
Input
The only line of standard input contains two integers \(R\) and \(K\) (\(1 \leq R, K \leq 1000\)) - the length and width of the Walimah hall in meters, separated by a space.
Output
Print a single integer - the maximum possible number of chairs that can be placed in the Walimah hall.
Scoring
| Subtask | Additional constraints | Points |
|---|---|---|
| \(1\) | \(R, K \le 5\) | \(8\) |
| \(2\) | \(\min(R, K) = 1\) | \(10\) |
| \(3\) | \(\min(R, K) \le 2\) | \(14\) |
| \(4\) | \(R \bmod 3 = 0\) and \(K \bmod 3 = 0\) | \(16\) |
| \(5\) | At least one of \(R, K\) is divisible by \(3\) | \(20\) |
| \(6\) | no additional constraints | \(32\) |
Example
Input
3 4
Output
10
Note
Explanation: The hall has \(3 \times 4 = 12\) square meters.
We can place \(2\) tables and use the remaining \(10\) squares for chairs. For example:
C C C C
C T C T
C C C C
Here, T represents a table and C represents a chair.
Every chair is placed next to at least one table, either by side or by corner. Since one table can have at most \(8\) chairs around it, placing only one table would not be enough for \(11\) chairs. Therefore, the maximum possible number of chairs is \(10\).
Solution
One table covers its own square and all eight neighbouring squares: a \(3\times3\) block. Therefore, at least
\[ \left\lceil\frac R3\right\rceil \cdot \left\lceil\frac K3\right\rceil \]
tables are needed. This bound is achievable by placing one table in every group of three rows and three columns.
All other squares can contain chairs, so subtract the minimum number of tables from the hall’s area. The complexity is \(O(1)\).
#include <iostream>
using namespace std;
int main() {
long long rows, columns;
cin >> rows >> columns;
long long tables = (rows + 2) / 3 * ((columns + 2) / 3);
cout << rows * columns - tables << '\n';
}