← 返回题目列表

Codeforces · 768/E

E. 石头游戏

中文机器翻译题面 查看原题

山姆一直在教乔恩玩石头游戏,以磨练他的思维并帮助他制定对抗异鬼的策略。这个游戏的规则非常简单:

- 游戏从 n 堆石子开始,索引从 1 到 n。第 i 堆包含 si 石头。
- 玩家交替采取行动。一次移动被认为是从一堆石头中移走一定数量的石头。移除 0 颗石子不算作一次移动。
- 无法移动的玩家失败。

现在乔恩相信他已经准备好战斗,但山姆不这么认为。为了证明他的论点,萨姆建议他们玩游戏的修改版本。

在此修改版本中,在一堆上不能进行多次移动。例如,如果从一堆石子中取出 4 个石子,则不能再从该堆中取出 4 个石子。

Sam 设置游戏并迈出第一步。乔恩认为山姆只是想阻止他参加战斗。乔恩想知道如果两人都发挥最佳状态,他是否能获胜。

输入

第一行由一个整数 n (1 ≤ n ≤ 106) 组成——堆的数量。

接下来的 n 行每一行都包含一个整数 si (1 ≤ si ≤ 60) — 第 i 堆石子的数量。

输出

如果 Jon 获胜,则打印包含“YES”(不带引号)的单行,否则打印“NO”(不带引号)

示例

输入 #1

1
5

输出 #1

NO

输入 #2

2
1
2

输出 #2

YES

注意

在第一种情况下,Sam 移走了所有石头,Jon 输了。

在第二种情况下,Sam 可以进行以下移动:$$\{1,2\} \rightarrow \{0,2\}、\{1,2\} \rightarrow \{1,0\}、\{1,2\} \rightarrow \{1,1\}$$

在每种情况下,乔恩都可以采取最后一步来赢得比赛,如下所示: $${ \{ 0, 2 \} } \rightarrow { \{ 0, 0 \} }, { \{ 1, 0 \} } \rightarrow { \{ 0, 0 \} }, { \{ 1, 1 \} } \rightarrow { \{ 0, 1 \} }$$