1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <cstdio>
#include <limits>
#include <vector>

int X[1000000];

int sprawdz(int n) {
    if (n == 1) {
	return X[0] == 1;
    }
    int count_endpoints = 0;
    int links = 2 * X[0];
    for (int i=1; i<n; ++i) {
	if (!X[i]) {
	    return false;
	}
	int min_links = (i==n-1) ? 0 : 1;
	links = 2 * X[i] - links;
	if (links < min_links) {
	    count_endpoints += min_links - links;
	    links = min_links;
	}
	if (count_endpoints > 2) {
	    return false;
	}
    }
    return (links == 0 && count_endpoints == 0) || (links + count_endpoints == 2);
}

int main() {
    int T; scanf("%d", &T);
    for (int IT=1; IT<=T; ++IT) {
	int n; scanf("%d", &n);

	int count = 0;
	bool running = false;
	for (int i=0; i<n; ++i) {
	    int number;
	    scanf("%d", &number);
	    if (number) {
		running = true;
	    }
	    if (running) {
		X[count++] = number;
	    }
	}
	while (count > 1 && !X[count-1]) {
	    --count;
	}
	printf("%s\n", sprawdz(count) ? "TAK" : "NIE");
    }
}