Problem H
Subtraction Plus Plus
Alex and Steve just got back home from a mining trip and now
have a lot of extra cobblestone. With their house already
built, they decide to play a game of subtraction. They take
turns subtracting from an initial stack of $N$ cobblestone. At a turn
$i$, the player can
subtract any amount of cobblestone from $1$ to $i$. For example, the first player who
goes must subtract exactly 1 cobblestone and the second player
can either subtract 1 or 2 cobblestone. The player who cannot
subtract anything loses. Alex always goes first. Will Alex win
if she plays optimally?
Input
The first line consists of $1$ integer, $1 \leq N \leq 5\, 000$, the initial
cobblestone stack size.
Output
Output “YES” if Alex will win, “NO” if otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
YES |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 |
YES |
