VNINGAME - Trò chơi

Johny and Margaret are playing “pebbles”. Initially there is a certain number of pebbles on a table, grouped in n piles. The piles are next to each other, forming a single row. The arrangement of stones satisfies an additional property that each pile consists of at least as many pebbles as the one to the left (with the obvious exception of the leftmost pile). The players alternately remove any number of pebbles from a single pile of their choice. They have to take care, though, not to make any pile smaller than the one left to it. In other words, the piles have to satisfy the initial property after the move as well. When one of the players cannot makeamove (i.e. before his move there are no more pebbles on thetable), he loses. Johny always starts, to compensate for Margaret ’s mastery in this game.
In fact Margaret is so good that she always makes the best move, and wins the game whenever she has a chance. Therefore Johny asks your help — he would like to know if he stands a chance of beating Margaret with aparticular initial arrangement. Write a programme that determines answers to Johny ’s inquiries.

Input

  • In the first line of the standard input there is a single integer u (0 < u < 11) denoting the number of initial pebble arrangements to analyse. The following 2u lines contain descriptions of these arrangements; each one takes exactly two lines. The first line of each description contains a single integer n, 0 < n < 1001 — the number of piles.
  • The second line of description holds n non-negative integers ai separated by single spaces and denoting the numbers of pebbles in successivepiles, left to right. These numbers satisfy the following inequality a1 <= a2 <= ... <= an. The total number of pebbles in any arrangement does not exceed 10000.

Output

Precisely u lines should be printed out on the standard output. The i-th of these lines (for 1 <= i <= u) should hold the word TAK (yes in Polish),if Johny can win starting with the i-th initial arrangement given in the input, or the word NIE (no in Polish), if Johny is bound to lose that game, assuming optimal play of Margaret.

Example

 
Input 
2
2
2 2
3
1 2 4
Output 
NIE
TAK


Được gửi lên bởi:Trần Hải Đăng
Ngày:2010-05-03
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:POI 2008

hide comments
2010-05-05 02:05:52 Nguyen Duc Tam
Thank you Hai Dang. Do đề không rõ ý đó nên mình thắc mắc không hiểu.
2010-05-04 07:04:41 Trần Hải Ðãng
Mỗi lần đi là lấy số viên sỏi tùy ý ở một đống nào đó, sao cho vẫn thỏa mãn tính chất không giảm của dãy
2010-05-04 05:04:19 Nguyen Duc Tam
Lấy tùy ý ở từng đống sỏi hay mỗi đống có thể lấy tùy ý. Xin Ps nói rõ giúp với. Thank!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.