← 返回题目列表

Codeforces · 1434/E

E. 凸游戏

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

鹿丸和阿斯玛喜欢玩不同的游戏,有时他们会玩以下游戏:给定越来越大的数字,他们轮流移动。每一步都包括从列表中选择一个数字。

假设所选号码为 $$$v_{i_1}$$$、$$$v_{i_2}$$$、$$$\ldots$$$、$$$v_{i_k}$$$。必须满足以下条件:

- $$$i_{j} < i_{j+1}$$$ 对于所有 $$$1 \leq j \leq k-1$$$;
- $$$v_{i_{j+1}} - v_{i_j} < v_{i_{j+2}} - v_{i_{j+1}}$$$ 对于所有 $$$1 \leq j \leq k-2$$$。

然而,只玩一个游戏很容易,所以今天鹿丸和阿斯玛决定同时玩$$$n$$$游戏。他们同意轮流玩一场,鹿丸先走。在每一回合中,玩家在任何一场游戏中执行有效的移动。不能移动的玩家就输了。找出谁获胜,前提是双方都发挥最佳。

输入

第一行包含唯一的整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) 代表鹿丸和阿斯玛同时玩的游戏数量。接下来的几行描述了游戏。

每个描述都从唯一的数字 $$$m$$$ ($$$m\geq 1$$$) 开始,表示数字列表的长度。第二行包含游戏中递增的空格分隔序列 $$$v_1$$$, $$$v_2$$$, ..., $$$v_m$$$ ($$$1 \leq v_{1} < v_{2} < ... < v_{m} \leq 10^{5}$$$)。

所有序列的总长度不超过$$$10^5$$$。

输出

如果鹿丸能够取得胜利,则打印“YES”,否则打印“NO”。

示例

输入 #1

1
10
1 2 3 4 5 6 7 8 9 10

输出 #1

YES

输入 #2

2
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10

输出 #2

NO

输入 #3

4
7
14404 32906 41661 47694 51605 75933 80826
5
25374 42550 60164 62649 86273
2
7002 36731
8
23305 45601 46404 47346 47675 58125 74092 87225

输出 #3

NO

注意

在第一个示例中,Shikamaru 可以选择最后一个数字,而 Asuma 由于第一个约束而无法执行任何操作。

在第二个样本测试中,阿斯玛可以遵循对称策略,每次在另一个实例中重复鹿丸的动作,因此获胜。