跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#LGP1288. 取数游戏 II

取数游戏 II

题目描述

一个环有 NN 个节点、NN 条边,每条边上有一个非负整数,至少有一条边的值是 0。硬币最初位于第一条边和最后一条边之间的节点。

两名玩家轮流行动。每次必须选择硬币旁边一条数值非 0 的边,将它的数值严格减小到任意一个非负整数,然后把硬币沿这条边移到另一端。

如果轮到某位玩家时,硬币两侧的边都为 0,该玩家就输。双方都采用最优策略,请判断先手是否必胜。

输入格式

第一行输入 NN。第二行按环上的顺序输入 NN 条边的数值。

输出格式

如果先手存在必胜策略,输出 YES;否则输出 NO。

数据范围

N≤20N\leq20,边上的数值为 0 至 30 的整数,且至少有一个 0。

样例 1

4
2 5 3 0
YES

样例 2

3
0 0 0
NO

来源

洛谷 P1288。保留原题署名,题意按原题整理;测试数据由本站独立构造。

相关

在下列比赛中:

数论与博弈