取石子游戏

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file stones.in Output file stones.out

【题目描述】

你和小伙伴在玩一个游戏,这个游戏是轮流从若干堆中拿石子。最初有N堆石子,每堆石子的个数是a1,a2,...,aN。每个回合,轮到的玩家必须从某堆石子中拿出至少一个石子,但拿的石子数不能超过这一堆石子数的一半。不能拿石子的玩家就输了。例如,有三堆石子,每堆分别有5,1,2个,那么玩家可以从第一堆中拿走1或2个石子,不能从第二堆中拿石子,可以从第三堆中拿走1个石子。注意,玩家不能从第二堆中拿石子的原因是1比1(该堆石子数量)的一半大。假定你先拿,并且你的朋友总是执行最佳策略,判断你是否有必胜策略。

【输入格式】

输入包含多组数据。

输入文件的第1行有一个正整数T(1<=T<=100),表示数据组数。

接下来是T组数据。

每组数据的第1行有一个正整数N(1<=N<=100),表示堆数。

每组数据的第2行有N个正整数a1,a2,...,aN(1<=ai<=2*10^18),表示每堆的石子数。

【输出格式】

对每组数据,若你有必胜策略则输出一行"YES",否则输出一行"NO"(均不带引号)。

【样例输入】

4 2 4 4 3 1 2 3 3 2 4 6 3 1 2 1

【样例输出】

NO
YES
NO
YES

【来源】

UVa1482 Playing With Stones

刘汝佳,《算法竞赛入门经典训练指南》表2.6