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?


The first line consists of $1$ integer, $1 \leq N \leq 5\, 000$, the initial cobblestone stack size.


Output “YES” if Alex will win, “NO” if otherwise.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
CPU Time limit 1 second
Memory limit 1024 MB
Lucas Xia
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in