OI题库

【题目描述】

你和小伙伴在玩一个游戏，这个游戏是轮流从若干堆中拿石子。最初有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