首页 > 代码库 > 石子游戏Kam（bzoj 1115）

石子游戏Kam（bzoj 1115）

2024-09-11 17:42:10   217人阅读

Description

有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。

Input

第一行u表示数据组数。对于每组数据，第一行N表示石子堆数，第二行N个数ai表示第i堆石子的个数(a1<=a2<=……<=an)。 1<=u<=10 1<=n<=1000 0<=ai<=10000

Output

u行，若先手必胜输出TAK，否则输出NIE。

Sample Input

2
2
2 2
3
1 2 4

Sample Output

NIE
TAK
/*
    因为要求后面的一定大于等于前面的，所以可以搞一个差分序列，那么每在i上取一个石子，就会在i+1上加一个石子，这样就变成了倒着的阶梯NIM。
    推荐一篇讲阶梯NIM的博客：http://blog.csdn.net/kk303/article/details/6692506 
*/
#include<iostream>
#include<cstdio>
#define N 1010
using namespace std;
int a[N],b[N],n;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i]-a[i-1];
        }
        int ans=0;
        for(int i=n;i>=1;i-=2)
            ans^=b[i];
        if(ans) printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}

 

石子游戏Kam（bzoj 1115）


联系
我们