Huge Pile

The only pile that matters is the future pile of size $k$. If it exists after some sequence of operations, it has an ancestry chain:

$$n \to x_1 \to x_2 \to \cdots \to k.$$

Each arrow is one split of the current ancestor pile. Any splits done elsewhere are just burning minutes for no benefit, so the answer is exactly the minimum depth where $k$ can appear in the binary split tree rooted at $n$.

Now the key observation: after exactly $d$ levels of splitting, the original pile has effectively been divided into $2^d$ almost-equal parts. Therefore every pile at depth $d$ has size either

$$\left\lfloor \frac{n}{2^d} \right\rfloor \quad \text{or} \quad \left\lceil \frac{n}{2^d} \right\rceil.$$

Why? For $d=0$, there is just one pile of size $n$, so it is true. If the claim is true for a pile size $x$, splitting it creates $\lfloor x/2 \rfloor$ and $\lceil x/2 \rceil$, which are exactly the two closest integer halves. Repeating this keeps the final pieces as balanced as possible. Equivalently, after $d$ splits, the $2^d$ descendant piles must sum to $n$ and differ by at most $1$, so their only possible values are the floor and ceiling of $n/2^d$.

So for each depth $d$, we only need to check:

$$k = \left\lfloor \frac{n}{2^d} \right\rfloor \quad \text{or} \quad k = \left\lceil \frac{n}{2^d} \right\rceil.$$

The first such $d$ is optimal because we scan depths in increasing order.

For integer arithmetic,

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

where $m=2^d$.

Edge cases:

• If $k=n$, depth $0$ works.
• If $k>n$, it is impossible because splitting never increases pile sizes.
• If $k=1$, it may take many splits, but with $n \le 10^9$, checking up to about $31$ depths is enough.

Complexity per test case is $O(\log n)$, with constant memory. Basically tiny. The CPU will not even notice this problem happened.