Game (Editorial)

Editorial

Game Analysis

You start with a pile of $N$ stones. Each move consists of:

• Splitting the pile into two unequal positive parts $x$ and $y$,

• Taking all stones from the smaller part,

• Leaving the opponent with the larger pile.

A player who cannot split the pile (i.e., pile size $1$) loses.

Key Observation

When you split a pile of size $N$ into $(x,y)$ with x < y, you take $x$ stones and leave the opponent with y = N - x stones.

So your first move is equivalent to: [ Choose x  such that  N - x > x. ]

After that, the opponent plays on a pile of size N - x.

This is a classic cold/hot position game. The fundamental fact:

[ The losing positions are exactly the powers of two. ]

Why?

• If $N$ is a power of two, every unequal split leaves a pile that is not a power of two. So every move gives the opponent a winning position.

• If $N$ is not a power of two, you can always choose a split that leaves the opponent with the largest power of two below $N$. That power of two is a losing position, so you force a win.

Thus:

[ You win iff N is not a power of two. ]

And if you want to force the opponent into the losing position:

[ Let p = 2^_2 N ,  the largest power of 2 less than N. ]

You must leave the opponent with $p$ stones:

[ N - x = p   x = N - p. ]

Final Answer Rule

[ If N is a power of two: 0 ] [ Otherwise: N - 2^_2 N ]

This gives the number of stones you should take on your first move.

C++ Implementation

#include <iostream>
using namespace std;

int main() {
    int N; 
    cin >> N;
    if ((N & (N - 1)) == 0) {
        cout << 0;
        return 0;
    }
    int p = 1;
    while ((p << 1) < N) {
        p <<= 1;
    }

    cout << (N - p);
    return 0;
}