Codeforces 50A Domino Piling Solution in C (One-Line Math Proof)

Domino Piling (50A) looks like a tiling or search problem at first, and you might be tempted to try placements one by one. In fact the answer is a single division. The interesting part is proving why that division is always achievable.

The problem in short

You have a rectangular board of M × N squares (1 ≤ M ≤ N ≤ 16) and an unlimited supply of 2 × 1 dominoes, which can be rotated. Dominoes cannot overlap and must lie entirely on the board. What is the maximum number of dominoes you can place?

Full statement: Codeforces 50A – Domino Piling.

Upper bound

Every domino covers exactly 2 squares, and there are M × N squares. So you can never place more than ⌊MN / 2⌋ dominoes.

That bound is always reachable

We only need one way to reach it:

• If N is even, fill every row with N/2 horizontal dominoes. Every square is covered, and we used MN/2 dominoes.
• If N is odd, fill each row with (N − 1)/2 horizontal dominoes, leaving the last column empty. That column has M squares, so place ⌊M/2⌋ vertical dominoes in it. At most one square on the whole board is left uncovered, which is exactly what ⌊MN/2⌋ allows.

So the answer is simply (M × N) / 2 using integer division.

Examples

• 2 × 4 board: 8 squares, so 4 dominoes, two horizontal ones per row.
• 3 × 3 board: 9 squares, so 4 dominoes. One square always stays empty because 9 is odd.

Solution in C

#include <stdio.h>

int main(void) {
    int m, n;
    scanf("%d %d", &m, &n);

    /* Every domino covers 2 squares, and a board can always be tiled
       leaving at most one square empty. */
    printf("%d\n", (m * n) / 2);
    return 0;
}

With M, N ≤ 16 the product is at most 256, so int is more than enough.

Complexity

O(1) time and memory.

What to take away

A pattern that shows up again and again in competitive programming: find a simple upper bound (here, area divided by 2), then show a construction that reaches it. When both match, you have the answer without any search. Compare this with 1A Theatre Square, where stones may overhang, so the answer rounds up instead of down.

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.

Codeforces 4A Watermelon Solution in C (Why w = 2 Is the Trap)

Watermelon (4A) has one of the highest solve counts on Codeforces, and also one of the highest first-attempt failure rates. The whole problem comes down to a single edge case. Before reading the solution, it is worth trying to find that edge case yourself.

The problem in short

Two friends buy a watermelon weighing w kilos (1 ≤ w ≤ 100). They want to cut it into two pieces so that each piece weighs an even number of kilos. The pieces do not have to be equal, but each must have positive weight. Print YES if such a split exists, otherwise NO.

Full statement: Codeforces 4A – Watermelon.

Thinking it through

If both pieces are even, their sum is even. So an odd w is immediately impossible.

If w is even, can we always do it? The smallest positive even number is 2, so try a split of 2 and w − 2. The second piece is even (even minus even), and it is positive as long as w > 2.

That leaves exactly one even weight that fails: w = 2. The only split into positive whole parts is 1 + 1, and 1 is odd.

So the rule is: YES if w is even and w > 2, otherwise NO.

Checking a few values

• w = 8 → 2 + 6 (or 4 + 4) → YES
• w = 7 → odd → NO
• w = 2 → only 1 + 1 → NO
• w = 4 → 2 + 2 → YES
• w = 1 → odd → NO

Solution in C

#include <stdio.h>

int main(void) {
    int w;
    scanf("%d", &w);

    /* Both parts must be even and positive, so w must be even and at least 4. */
    if (w % 2 == 0 && w > 2)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

Complexity

One comparison: O(1) time and memory.

Why so many people fail it

The natural first submission is if (w % 2 == 0), which passes every sample and fails on w = 2. The habit to build from this problem is simple: after you write a condition, test it on the smallest valid inputs (here 1, 2, 3, 4) before submitting. Small inputs are where “obvious” rules break.

You may also notice that I removed the 1 ≤ w ≤ 100 range check that some solutions include. The judge guarantees the constraints, so checking them only adds code that can be wrong.

Practice next

For more problems where a tiny observation replaces the whole algorithm, try 50A Domino Piling and 1A Theatre Square.