1AUnreviewed1000GPT-5.4 (high)

Theatre Square

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Don’t think about area first. Since tiles can’t be broken and must stay axis-parallel, try solving the problem in one dimension: how many segments of length $a$ are needed to cover a length $n$ ?

To cover a side of length $n$ with tiles of side $a$ , you need the smallest integer $k$ such that $k \cdot a \ge n$ . That’s exactly $k = \left\lceil \frac{n}{a} \right\rceil.$

Now do the same for the other side: along width $m$ , you need $\left\lceil \frac{m}{a} \right\rceil$ tiles. The two directions are independent, which is the whole trick.

So the total number of square flagstones is the product of the counts along both dimensions: $\left\lceil \frac{n}{a} \right\rceil \cdot \left\lceil \frac{m}{a} \right\rceil.$ Area-based thinking is a trap here, because leftover strips still force whole extra tiles.

Implement the ceiling without floating point: $\left\lceil \frac{x}{a} \right\rceil = \frac{x + a - 1}{a}$ using integer division. Then compute $\text{ans} = \frac{n+a-1}{a} \cdot \frac{m+a-1}{a}.$ Use long long, because the answer can be as large as about $10^{18}$ , and int will absolutely eat shit.

Key observation

This problem is almost insultingly simple once you stop overthinking it.

You have a rectangle of size $n \times m$ , and square tiles of size $a \times a$ .

Tiles cannot be broken.
Tiles must stay parallel to the square.
It’s okay if they stick out past the border.

That means coverage in the two dimensions is completely independent.

Reduce to one dimension

Suppose you only want to cover a segment of length $n$ using pieces of length $a$ . How many do you need?

You need the smallest integer $k$ such that

$k \cdot a \ge n.$

That is exactly

$k = \left\lceil \frac{n}{a} \right\rceil.$

Same logic for the other side:

$\left\lceil \frac{m}{a} \right\rceil.$

Total number of flagstones

Since each tile occupies one “row slot” and one “column slot”, the total number is

$\left\lceil \frac{n}{a} \right\rceil \cdot \left\lceil \frac{m}{a} \right\rceil.$

That’s it. No DP, no geometry wizardry, no sacrifice to the gods of Codeforces.

Integer ceiling trick

Do not use floating point here. There’s zero reason to invite precision weirdness to a kindergarten math problem.

For positive integers,

$\left\lceil \frac{x}{a} \right\rceil = \frac{x + a - 1}{a}$

using integer division.

So:

$\text{rows} = \frac{n+a-1}{a}, \qquad \text{cols} = \frac{m+a-1}{a}.$

Then

$\text{answer} = \text{rows} \cdot \text{cols}.$

Important implementation detail

The constraints go up to $10^9$ . The answer can be as large as roughly

$10^9 \cdot 10^9 = 10^{18},$

so int is not enough. Use long long.

Complexity

The algorithm is constant time:

$O(1)$

with

$O(1)$

extra memory.

Short, clean, and brutally effective.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n, m, a;
    cin >> n >> m >> a;

    ll x = (n + a - 1) / a;
    ll y = (m + a - 1) / a;

    cout << x * y << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n, m, a;
    cin >> n >> m >> a;

    ll x = (n + a - 1) / a;
    ll y = (m + a - 1) / a;

    cout << x * y << '\n';
    return 0;
}

View on Codeforces Back to the list