记录编号	401382	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009]取石子游戏	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2017-05-02 12:02:29	内存使用	8.08 MiB

//KZNS
#include <cstdio>
using namespace std;
#define Nmax 1010
int N;
int S[Nmax];
void init() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", &S[i]);
}
int L[Nmax][Nmax], R[Nmax][Nmax];
void work() {
	for (int i = 1; i <= N; i++)
		L[i][i] = R[i][i] = S[i];
	int a, b, x;
	for (int k = 2; k <= N; k++) {
		for (int i = 1; i+k-1 <= N; i++) {
			int j = i+k-1;
			a = L[i][j-1];
			b = R[i][j-1];
			x = S[j];
			if (b == x)
				L[i][j] = 0;
			else if (a > x && b > x)
				L[i][j] = x;
			else if (b < x && x <= a)
				L[i][j] = x-1;
			else if (a <= x && x < b)
				L[i][j] = x+1;
			else
				L[i][j] = x;

			a = L[i+1][j];
			b = L[i+1][j];
			x = S[i];
			if (a == x)
				R[i][j] = 0;
			else if (a > x && b > x)
				R[i][j] = x;
			else if (a < x && x <= b)
				R[i][j] = x-1;
			else if (b <= x && x < a)
				R[i][j] = x+1;
			else
				R[i][j] = x;
		}
	}
	if (S[1] == L[2][N])
		printf("0\n");
	else
		printf("1\n");
}
int main() {
	freopen("zjoi09stone.in", "r", stdin);
	freopen("zjoi09stone.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--) {
		init();
		work();
	}
	return 0;
}
//UBWH