#2288. 江南乐

江南乐

江南乐

题目描述

第4 页,共5 页 

第3 题:江南乐(game),运行时限3s,内存上限512M 【问题描述】

小A 是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项 之后,小A 有一天突然想起了他小时候在江南玩过的一个回合制游戏。 游戏的规则是这样的,首先给定一个数F,然后游戏系统会产生T 组游戏。每一组游戏包 含N 堆石子,小A 和他的对手轮流操作。每次操作时,操作者先选定一个不小于2 的正整数 M(M 是操作者自行选定的,而且每次操作时可不一样),然后将任意一堆数量不小于F 的石 子分成M 堆,并且满足这M 堆石子中石子数最多的一堆 至多 比石子数最少的一堆多1(即 分的尽量平均,事实上按照这样的分石子方法,选定M 和一堆石子后,它分出来的状态是固 定的)。当一个玩家不能操作的时候,也就是当每一堆石子的数量都严格小于F 时,他就输掉 了。(补充:先手从N 堆石子中选择一堆数量不小于F 的石子分成M 堆后,此时共有N+M-1 堆石子,接下来小A 从这N+M-1 堆石子中选择一堆数量不小于F 的石子,依此类推。)

小A 从小就是个有风度的男生,他邀请他的对手作为先手。小A 现在想要知道,面对给 定的一组游戏,而且他的对手也和他一样聪明绝顶的话,究竟谁能够获得胜利? 【输入格式】 输入文件为game.in。 输入第一行包含两个正整数T 和F,分别表示游戏组数与给定的数。

接下来T 行,每行第一个数N 表示该组游戏初始状态下有多少堆石子。之后N 个正整数, 表示这N 堆石子分别有多少个。 【输出格式】 输出文件为game.out。 输出一行,包含T 个用空格隔开的0 或1 的数,其中0 代表此时小A(后手)会胜利,而 1 代表小A 的对手(先手)会胜利。

2014‐05‐11  第5 页,共5 页  【输入输出样例】 game.in game.out 4 3 1 1 1 2 1 3 1 5 0 0 1 1 【数据范围】

对于10%的数据,T=1,N=1,F≤1,每堆石子数量≤10;

对于20%的数据,T≤100,N≤2,F≤1,每堆石子数量≤10;

对于30%的数据,T≤100,N≤100,F≤1,每堆石子数量≤10;

对于40%的数据,T≤100,N≤100,F≤5,每堆石子数量≤15;

对于70%的数据,T≤100,N≤100,F≤1000,每堆石子数量≤1000;

对于100%的数据,T≤100,N≤100,F≤100000,每堆石子数量≤100000。

以上所有数均为正整数。 【编译命令】

对于c++语言: g++ -o game game.cpp –lm 对于c语言: gcc -o game game.c –lm 对于pascal语言: fpc game.pas

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 3
1 1
1 2
1 3
1 5
0 0 1 1