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
#include <iostream>
#include <vector>

using namespace std;

void checkOne();

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        checkOne();
    }
}

void checkOne() {
    vector<int> a;
    int n, lastNonZero = 0;
    cin >> n;
    a.resize(n + 2);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > 0) lastNonZero = i;
    }
    int start = 0;
    while (a[start] == 0) {
        ++start;
    }
    bool force = false;
    if (start == lastNonZero) {
        cout << (a[start] == 1 ? "TAK\n" : "NIE\n");
        return;
    }
    while (start <= lastNonZero) {
        if (a[start] == 0) {
            cout << "NIE\n";
            return;
        }
        if (!force) {
            int sub = min(a[start], a[start + 1]);
            a[start] -= sub;
            a[start + 1] -= sub;
        } else {
            if (a[start + 1] > a[start] - 1) {
                a[start + 1] -= a[start] - 1;
                a[start] = 0;
            } else {
                a[start] -= a[start + 1];
                a[start + 1] = 0;
            }
        }
        if (a[start] > 1) {
            cout << "NIE\n";
            return;
        }
        if ((a[start] == 1 || force) && a[start + 1] == 0 && lastNonZero > start + 1) {
            cout << "NIE\n";
            return;
        }
        if (a[start + 1] == 0 && start < lastNonZero) {
            force = true;
            ++start;
        }
        ++start;
    }
    cout << "TAK\n";
}