Hourglass

Let $x$ be the amount of sand currently on top, measured in minutes of falling time. If Vadim never touched the hourglass again, the sand would keep falling for exactly $x$ more minutes.

Initially, after the flip at time $0$, we have

$x=s.$

Now suppose $d$ minutes pass. Before any next flip, the top pile has

$\max(0,x-d)$

minutes left. Everything else is on the bottom. Since the whole hourglass contains $s$ minutes of sand, after flipping, the new top pile becomes

$s-\max(0,x-d).$

For the regular flips, $d=k$, so one scheduled flip applies

$f(x)=s-\max(0,x-k).$

At first this looks like simulation, but $s,k,m\le 10^9$, so simulating flips is a great way to get cooked by the constraints. We need the pattern.

Start from $x=s$.

After one flip:

$f(s)=s-\max(0,s-k).$

So:

• if $s\le k$, then $f(s)=s$;
• if $s>k$, then $f(s)=k$.

That means after one flip, the state is simply

$\min(s,k).$

Now apply one more flip. Since $\min(s,k)\le k$, all currently top sand has already fallen before the next scheduled flip, or exactly finishes at it. Therefore:

$f(\min(s,k))=s.$

So the process alternates:

$s,\ \min(s,k),\ s,\ \min(s,k),\ldots$

where the value is the state immediately after a scheduled flip.

Let

$n=\left\lfloor\frac{m}{k}\right\rfloor$

be the number of scheduled flips Vadim performs before leaving. If $m$ is exactly divisible by $k$, the flip at time $m$ is included, as the statement says he still does it in the last minute.

Let

$r=m\bmod k$

be the number of minutes after the last performed flip before he leaves.

Immediately after the last flip:

• if $n$ is even, $x=s$;
• if $n$ is odd, $x=\min(s,k)$.

Then $r$ more minutes pass with no further flip. The remaining falling time after Vadim leaves is

$\max(0,x-r).$

That is the whole solution. The main false assumption to kill is thinking the exact history of partial flips matters. It doesn’t. The state collapses into a 2-cycle immediately, which is why this is math, not simulation.

Edge cases:

• If $m<k$, then $n=0$, no scheduled flip happens before leaving, and the answer is $\max(0,s-m)$.
• If $m$ is divisible by $k$, then $r=0$, and the last flip happens exactly when Vadim leaves.
• If $s\le k$, the hourglass fully empties before each flip, so every flip resets it to $s$; the formula still works because $\min(s,k)=s$.

Complexity per test case is $O(1)$ time and $O(1)$ memory.