Unfair Game

The big trap is assuming Alice’s lack of exact knowledge forces some complicated information-game DP. It doesn’t. The extra information from Bob is mostly noise. Alice only needs to know whether the current number is even, and Bob’s response gives that every time: $x=0$ means odd, $x>0$ means even, and $-1$ means she already won.

Consider the optimal move for a known number.

If $a$ is odd, Alice cannot halve, so she must do $a \to a-1.$

If $a$ is even, halving is always optimal. Subtracting $1$ makes the number odd and does not remove the main binary scale efficiently. More formally, the greedy value $f(a)=\lfloor \log_2 a \rfloor + \operatorname{popcount}(a)$ satisfies:

• for odd $a$, subtracting $1$ decreases the popcount by $1$;
• for even $a$, halving removes one binary position and preserves popcount;
• subtracting from an even number is never better than halving.

So Alice’s optimal strategy is:

• if the number is even, halve it;
• otherwise, subtract $1$.

This strategy depends only on parity, which Alice always knows. Nice little fakeout.

Now count the numbers that require more than $k$ moves.

For any positive integer $a$, the number of moves is $f(a)=\lfloor \log_2 a \rfloor + \operatorname{popcount}(a).$

Why? Every halving shifts the binary representation right. A number with highest bit position $l$ needs exactly $l$ halvings under the greedy process. Every $1$ bit eventually becomes the last bit and must be removed by one subtract operation, so there are exactly $\operatorname{popcount}(a)$ subtracts.

Let $n=2^d$.

For numbers with highest bit $l<d$, they lie in $[2^l,2^{l+1}-1].$ Their top bit is fixed as $1$, and there are $l$ lower bits. If $q$ of those lower bits are set, then $\operatorname{popcount}(a)=1+q,$ so $f(a)=l+1+q.$

Such a number is winnable within $k$ moves iff $l+1+q\le k,$ or $q\le k-l-1.$

For this fixed $l$, the number of winnable values is therefore $\sum_{q=0}^{\min(l,k-l-1)} {l\choose q},$ with zero contribution if $k-l-1<0$.

The remaining number is exactly $2^d$. Its move count is $d+1,$ so it contributes one more winnable value if $d+1\le k$.

Let good be the total number Alice can win within $k$ moves. The answer is simply $n-good.$

Edge cases are clean:

• If $n=1$, then $d=0$, and Alice wins in one subtract move. Since $k\ge 1$, the answer is $0$.
• If $k$ is huge, the binomial sums naturally count all numbers, so the answer becomes $0$.

The maximum possible $d$ is tiny because $n\le 10^9$, so precomputing binomial coefficients is more than enough.

Complexity per test case: $O(d^2),$ which is effectively constant here. Memory usage is $O(d^2).$