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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
#include <vector>

using zabawki_t = std::vector< int >;

bool sprawdzaj(zabawki_t& zabawki) {

	if (zabawki.size() == 1) {
		return zabawki[0] <= 1;
	}

	int const ostatni = zabawki.size() - 1;
	int pocz_kon = 0;

	// 2 1 ...
	if (zabawki[0] - 1 == zabawki[1]) {
		// zaczynam i koncze w pierwszym
		pocz_kon += 2;
	}
	else if (zabawki[0] == zabawki[1]) {
		// zaczynam lub koncze
		pocz_kon += 1;
	}

	// ... 1 2
	if (zabawki[ostatni - 1] == zabawki[ostatni] - 1) {
		// zaczynam i koncze w ostatnim
		pocz_kon += 2;
	}
	else if (zabawki[ostatni - 1] == zabawki[ostatni]) {
		pocz_kon += 1;
	}

	if (2 < pocz_kon) {
		return false;
	}

	for (int i = 0; i <= zabawki.size(); ++i) {
		if ((0 < i) && (i < ostatni) && (0 < zabawki[i-1])) {
			if (zabawki[i] == zabawki[i-1] + zabawki[i+1]) {
				pocz_kon += 1;
			}
			else if (zabawki[i] == zabawki[i-1] + zabawki[i+1] + 1) {
				// poczatek i koniec, np. 2 4 1
				pocz_kon += 2;
			}
		}

		if (2 < pocz_kon) {
			return false;
		}

		if ((0 < i) && (i <= ostatni)) {
			int wsp = std::min(zabawki[i-1], zabawki[i]);
			zabawki[i-1] -= wsp;
			zabawki[i]   -= wsp;
		}

		// ostatnia iteracja dla i = zabawki.size()
		if (2 <= zabawki[i-1]) {
			return false;
		}
	}

	return pocz_kon <= 2;
}

int main() {
	std::istream& WEJ = std::cin;
	//std::ifstream WEJ("debug.in");
	//std::ifstream WEJ("t5.in");

	int l_dni; WEJ >> l_dni;

	for (int i = 0; i < l_dni; ++i) {
		int l_zabawek; WEJ >> l_zabawek;

		zabawki_t zabawki;
		for (int i = 0; i < l_zabawek; ++i) {
			int ile; WEJ >> ile;
			if ((0 == zabawki.size()) && (0 == ile)) continue;

			zabawki.push_back(ile);
		}
		while((0 < zabawki.size()) && (zabawki.back() == 0)) zabawki.pop_back();

		if (sprawdzaj(zabawki)) {
			std::cout << "TAK\n";
		}
		else {
			std::cout << "NIE\n";
		}
	}
}