1485. [UVa 1482] 取石子游戏

【题目描述】

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

【输入格式】

输入包含多组数据。

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

接下来是 $T$ 组数据。

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

每组数据的第 $2$ 行有 $N$ 个正整数 $a_1,a_2,...,a_N(1<=a_i<=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

【来源】

UVa 1482 Playing With Stones

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