Problem : 20 - 堆石頭遊戲

Problem Statistics

Solved Member: 26　　Submission: 125　　User Tried: 30

Statement:

世界上最聰明的你正在和Kannaduki玩一個很老梗的遊戲－取石子。規則是這樣的，桌子上面有很多疊石頭，每疊的數量不一定相等，但是右邊的石頭數量一定大於等於左邊的。你和Kannaduki各要從其中任意一疊拿走任意顆石子(你可以只拿一顆，也可以把整疊拿走，但是不可以不拿)。

每一場最開始有N疊石頭，每疊至少有1顆石頭。第一個拿的人會是你，然後兩個人輪流拿，直到某一次某個人把整個桌面上的石頭都拿光了，那個人就是贏家。拿完某堆之後，必須使這堆石頭至少與左邊那疊的數量相等

你是世界上最聰明的人，想當然爾你會挑選最佳的拿法來電Kannaduki。另外，雖然Kannaduki沒你聰明，不過由於他遊戲前偷偷買了攻略本，所以你可以假設他也會依照最佳的方法來取石頭。

Task:

給你每次遊戲最開始時候的狀態，假如你會贏，請你輸出"TAK"，如果你不會贏，就輸出"NIE"。

Input:Output:

最剛開始有一個正整數T(1 <= T <= 10)，代表後來有幾場遊戲。
每一場遊戲開始有一個N(1 <= N <= 1000)，代表桌上有N疊石頭。
接下來有N個正整數，依序為每疊石頭的石頭數目。另外Kannaduki很好心，他已經幫你把石子數由小到大排序一遍了。

每一場遊戲請你輸出一行，假如你會贏的話請輸出"TAK"，相反的，請你輸出"NIE"。

Sample Input:Sample Output:

2
2
2 2
3
1 2 4

NIE
TAK

HINT:

示意圖：

Source:

POI 16 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-ocen	1000ms	131072kb
1	1000ms	131072kb	7
2-ocen	1000ms	131072kb
2	1000ms	131072kb	7
3-ocen	1000ms	131072kb
3	1000ms	131072kb	7
4-ocen	1000ms	131072kb
4	1000ms	131072kb	7
5-ocen	5000ms	131072kb
5	1000ms	131072kb	7
6	1000ms	131072kb	7
7	1000ms	131072kb	7
8	1000ms	131072kb	7
9	1000ms	131072kb	7
10	1000ms	131072kb	7
11	1000ms	131072kb	7
12	1000ms	131072kb	7
13	1000ms	131072kb	8
14	1000ms	131072kb	8