Codeforces 1A Theatre Square Solution in C (Ceiling Division Explained)

Theatre Square is problem 1A, the very first problem in the Codeforces archive, and it is where most people meet two ideas they will use for years: ceiling division and integer overflow. The code is only a few lines, but almost every beginner gets a Wrong Answer on it at least once. Here is why, and how to get it right the first time.

The problem in short

A rectangular square measures n by m meters. We want to pave it with square stones of side a. Stones cannot be cut or rotated diagonally, and they are allowed to stick out past the edge of the square. What is the smallest number of stones that covers the whole area? All three numbers can be as large as 10⁹.

Full statement: Codeforces 1A – Theatre Square.

Key idea: treat each side separately

Because the stones are aligned with the sides, the two directions are independent. Along the side of length n we need enough stones to reach or pass the edge, which is n / a rounded up. The same goes for the side of length m. The grid of stones is just those two counts multiplied together:

answer = ⌈n / a⌉ × ⌈m / a⌉

There is no cleverer packing: any row of stones along the n side has to contain at least ⌈n/a⌉ stones, and you need at least ⌈m/a⌉ such rows.

Rounding up without floating point

C's integer division rounds down. A common trick for positive integers is:

ceil(n / a) == (n + a - 1) / a

Adding a − 1 pushes any value with a remainder over to the next multiple, while exact multiples stay where they are. For example, with n = 6 and a = 4: (6 + 3) / 4 = 9 / 4 = 2. With n = 8: (8 + 3) / 4 = 11 / 4 = 2, which is still correct because 8 is an exact multiple.

Avoid ceil((double)n / a). It usually works, but floating-point rounding is a habit that will eventually bite you on bigger values.

Walking through the sample

6 6 4

Along each side we need ⌈6/4⌉ = 2 stones, so the answer is 2 × 2 = 4. The stones cover an 8 × 8 area, overhanging the square by 2 meters on two sides, which is allowed.

The overflow trap

Take n = m = 10⁹ and a = 1. The answer is 10¹⁸, far beyond what a 32-bit int can hold (about 2.1 × 10⁹). The fix is to use long long for every variable, read with %lld, and print with %lld. Making only the result long long is not enough if the multiplication itself is done in int.

Solution in C

#include <stdio.h>

int main(void) {
    long long n, m, a;
    scanf("%lld %lld %lld", &n, &m, &a);

    /* ceil(n / a) without floating point */
    long long along_n = (n + a - 1) / a;
    long long along_m = (m + a - 1) / a;

    printf("%lld\n", along_n * along_m);
    return 0;
}

Complexity

A constant number of arithmetic operations: O(1) time and O(1) memory.

Common mistakes

• Using int and overflowing on large tests.
• Computing the area (n × m) / (a × a). This ignores that stones cannot be cut, so it undercounts.
• Adding 1 to n / a unconditionally, which overcounts when n is an exact multiple of a.

Practice next

If ceiling division clicked, try 50A Domino Piling, which is the “floor” version of a tiling question, and 4A Watermelon for another one-line math observation.