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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <set>

int c;

void SKIP_WHITESPACE() {
    while (1) {
        c = fgetc(stdin);
        if (c != ' ' && c != '\n' && c != '\r')
            break;
    }
}

int READ_INT() {
    SKIP_WHITESPACE();
    int ret = c - '0';
    while (1) {
        c = fgetc(stdin);
        if (c < '0' || c > '9')
            break;
        ret = ret * 10 + c - '0';
    }
    return ret;
}

int n, t, i, j, x, ti;

union elem {
    uint64_t w;
    struct {
        unsigned r : 30;
        unsigned p : 1;
        unsigned k : 1;
        unsigned l : 30;
        unsigned v : 2;
    }s;

    bool operator<(const elem& par) const {
        return w < par.w;
    }
    bool operator==(const elem& par) const {
        return w == par.w;
    }
};

std::set<elem> col[2];
int cur, next, nr, nl;
elem E, F1, F2, f, g;

int main(int argc, char* argv[]) {
    std::ios_base::sync_with_stdio (false);

    E.w = 0;
    F1.s.r = 0; F1.s.l = 0; F1.s.p = 1; F1.s.k = 1; F1.s.v = 1;
    F2.s.r = 0; F2.s.l = 0; F2.s.p = 1; F2.s.k = 1; F2.s.v = 2;

    t = READ_INT();
    for (ti = 0; ti < t; ti++) {
        col[0].clear();
        col[1].clear();
        cur = 0;
        next = 1;
        col[0].insert(E);

        n = READ_INT();
        for (i = 0; i < n; ++i) {
            x = READ_INT();

            for (const auto& e : col[cur]) {
                if (x == 0) {
                    if (e == E) {
                        col[next].insert(e);
                    } else if (e == F1 || e == F2) {
                        col[next].insert(F2);
                    }
                    continue;
                }
                if (e.s.v == 2)
                    continue;
                if (e.s.l == 0 && e.s.r == 0 && e.s.v == 1)
                    continue;
                nr = x - e.s.l;
                nl = x - e.s.r;
                if (nr < 0 || nl < 0)
                    continue;
                f.s.l = nl; f.s.r = nr; f.s.p = e.s.p; f.s.k = e.s.k; f.s.v = 1;
                col[next].insert(f);
                if (e.s.p == 0 && nl > 0) {
                    g = f;
                    g.s.l = nl - 1;
                    g.s.p = 1;
                    col[next].insert(g);
                }
                if (e.s.k == 0 && nr > 0) {
                    g = f;
                    g.s.r = nr - 1;
                    g.s.k = 1;
                    col[next].insert(g);
                }
                if (e.s.p == 0 && e.s.k == 0 && nl > 0 && nr > 0) {
                    g = f;
                    g.s.l = nl - 1;
                    g.s.p = 1;
                    g.s.r = nr - 1;
                    g.s.k = 1;
                    col[next].insert(g);
                }
            }
            cur = (cur + 1) & 1;
            next = (next + 1) & 1;
            col[next].clear();
        }

        if (col[cur].count(F1) + col[cur].count(F2) > 0)
            std::cout << "TAK\n";
        else
            std::cout << "NIE\n";
    }
    return EXIT_SUCCESS;
}