做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2950. -- 「一本通 6.7 练习 5」取石子游戏

2950: 「一本通 6.7 练习 5」取石子游戏

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

原题来自:ZJOI 2009

在研究过 Nim 游戏及各种变种之后,Orez 又发现了一种全新的取石子游戏,这个游戏是这样的:

nnn 堆石子,将这 nnn 堆石子摆成一排。游戏由两个人进行,两人轮流操作,每次操作者都可以从最左或最右的一堆中取出若干颗石子,可以将那一堆全部取掉,但不能不取,不能操作的人就输了。

Orez 问:对于任意给出一个初始一个局面,是否存在先手必胜策略。

输入

第一行为一个整数 TTT,表示有 TTT 组测试数据。

对于每组测试数据,第一行为一个整数 nnn,表示有 nnn 堆石子,第二行为 nnn 个整数 aia_iai,依次表示每堆石子的数目。

输出

对于每组测试数据仅输出一个整数 000111。其中 111 表示有先手必胜策略,000 表示没有。

提示

样例输入

1
4
3 1 9 4

样例输出

0

对于 30%30\%30% 的数据,n≤5,ai≤105nle 5,a_ile 10^5n5,ai105
对于全部数据,1≤T≤10,1≤n≤10001le Tle 10,1le nle 10001T10,1n1000,每堆石子的个数小于等于 10910^9109

标签

[上一题][提交][讨论版][状态][下一题]