theatre-square

Theatre Square

We are tasked with tiling a grid of dimensions \(N \times M\) using tiles of dimensions \(A \times A\). The tiles are allowed to protrude the grid but must fully cover it.

Solution

If we consider the number of tiles needed to span the vertical dimension of the grid we find that its \(\lceil \frac{N}{A} \rceil\) and likewise, the tiles needed to span the horizontal dimension would be \(\lceil \frac{M}{A} \rceil\).

Therefore, the number of tiles needed to span the full grid is: \(\lceil \frac{N}{A} \rceil \times \lceil \frac{M}{A} \rceil\).

Ceil of integer division

Refered to as \(\lceil \frac{A}{B} \rceil\)

Written in C++ as: (A + B - 1) / B

#include<iostream>
using namespace std;

int main () {
    int n, m, a;
    cin >> n >> m >> a;

    long long v = (n + a - 1) / a;
    long long h = (m + a - 1) / a;

    cout << v * h;
}

Overflow

If \(N, M = 10^9\) and \(A = 1\) the answer would be \(N \times M = 10^{18}\). int will overflow so we need to use long long.