Towers of Boxes

Research check: the official Codeforces statement, the official contest editorial, and a public C++ solution on GitHub all reduce the problem to the same formula: compute the maximum tower height, then do ceiling division.

Consider a single tower with $h$ boxes.

For a box, the only thing that matters is how many boxes are above it. Since every box has weight $m$, if there are $x$ boxes above some box, then the load on it is $xm$.

The most loaded box is the bottom box, because it has all other $h-1$ boxes above it. So the whole tower is safe iff the bottom box is safe:

$(h-1)m \le d.$

Solving for $h$:

$h-1 \le \left\lfloor\frac d m\right\rfloor,$

so the maximum number of boxes in one tower is

$k=\left\lfloor\frac d m\right\rfloor+1.$

That is the whole trick. No DP, no greedy ordering, no weird box identity nonsense. The boxes are identical, so once we know the maximum valid tower size, the rest is just packing $n$ items into bins of capacity $k$.

Now we need the minimum number of towers. If we use $q$ towers, they can contain at most $qk$ boxes total. Therefore we must have

$qk \ge n,$

which means

$q \ge \left\lceil\frac n k\right\rceil.$

This lower bound is achievable: fill towers with $k$ boxes each, and put the leftover boxes into one final tower if needed. Since the leftover is at most $k$, that final tower is also valid. So the optimal answer is exactly

$\left\lceil\frac n {\left\lfloor d/m\right\rfloor+1}\right\rceil.$

Implementation detail: integer ceiling division for positive integers is

$\left\lceil\frac n k\right\rceil = \frac{n+k-1}{k}$

using integer division.

Edge cases:

• If $d<m$, then $\left\lfloor d/m\right\rfloor=0$, so $k=1$. No two boxes can be stacked, and the answer is $n$.
• If $k\ge n$, all boxes fit in one tower, answer $1$.
• If $n$ is divisible by $k$, the formula correctly avoids making a fake extra tower.

Complexity is $O(t)$ time and $O(1)$ memory. Tiny constraints, but the formula would survive much larger ones too.