Domino piling

Domino piling

Codeforces easy

Given a grid of \(N\) rows and \(M\) columns. You have an infinite amount of pieces of size \(2 \times 1\) you want to put as many pieces in the grid as possible such that.

1. Each piece completely covers two squares.

2. No two pieces overlap.

3. Each piece lies entirely inside the grid.

Solution

In this problem we have 3 cases. Let’s analyze them:

• \(N\) is even (N % 2 == 0):
  We can cover the entire grid by placing the pieces vertically.
  The number of pieces used is \[ \frac{N \times M}{2} \] because the grid has \(N \times M\) cells and each domino covers 2 cells.

• \(M\) is even (M % 2 == 0):
  We can cover the entire grid by placing the domino pieces horizontally.
  The number of pieces is \[ \frac{N \times M}{2} \]

• Both \(N\) and \(M\) are odd (N % 2 == 1 and M % 2 == 1):
  We place vertical pieces first, which leaves one full row uncovered (since \(N\) is odd).
  In that row, we place horizontal pieces, leaving exactly one cell uncovered (since \(M\) is odd).
  Therefore the number of dominoes used is \[ \frac{N \times M - 1}{2} \]

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    if (N % 2 == 0) {
        cout << (N * M) / 2 << endl;
    }
    else if (M % 2 == 0) {
        cout << (N * M) / 2 << endl;
    }
    else {
        cout << (N * M - 1) / 2 << endl;
    }
}