Domino Piling
Given a board of size \(M \times N\) and unlimited \(2\times1\) dominoes (rotation allowed), place as many dominoes as possible so that they lie entirely within the board and do not overlap. Output the maximum number of dominoes.
Solution
Each domino covers exactly two squares, so no tiling can use more than \(\left\lfloor \dfrac{MN}{2} \right\rfloor\) dominoes.
Checkerboard proof (upper bound). Color the \(M\times N\) board like a chessboard, and let \(B\) and \(W\) be the sets of black and white squares. Every \(2\times1\) domino always covers one black and one white square, so any packing uses at most \(\min\bigl(\lvert B\rvert,\lvert W\rvert\bigr)\). If \(MN\) is even, \(\lvert B\rvert=\lvert W\rvert=MN/2\); if \(MN\) is odd, they differ by 1. Hence \(\max \text{ dominoes } \le \left\lfloor \dfrac{MN}{2} \right\rfloor .\)
Achievability (explicit constructions).
- If at least one of \(M\) or \(N\) is even: tile the entire board (get \(MN/2\) dominoes).
- If both \(M\) and \(N\) are odd: fill all but one square, getting \(\dfrac{MN-1}{2}\) dominoes.
Therefore, in all cases the maximum number equals \(\left\lfloor \dfrac{MN}{2} \right\rfloor\).
For integers, \(\left\lfloor \dfrac{MN}{2}\right\rfloor\) is just (M*N)/2 using integer division.
#include <iostream>
using namespace std;
int main() {
long long M, N;
cin >> M >> N;
cout << (M * N) / 2; // floor(M*N/2)
}Although here \(1 \le M \le N \le 16\) so int is safe, using long long (as above) is a good habit for similar problems to avoid accidental overflow when products grow large.