Hide

Problem H
Subtraction Plus Plus

/problems/subtractionplusplus/file/statement/en/img-0001.png

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
CPU Time limit 1 second
Memory limit 1024 MB
Author
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