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
#include <cstdlib>
#include <cstdio>

int times_chosen[1024 * 1024];

enum class state_t {
    none_found,
    one_found,
    both_found,
};

bool do_single_case() {
    int n;
    scanf("%d\n", &n);

    int first_nonzero = -1;
    int last_nonzero = -1;
    int count_zeros = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &times_chosen[i]);

        if (times_chosen[i] != 0) {
            last_nonzero = i;
            if (first_nonzero == -1) {
                first_nonzero = i;
            }
        } else {
            count_zeros++;
        }
    }

    if (first_nonzero == -1) {
        // All zeros - not really a valid test case, but whatever
        // printf("all zeros\n");
        return false;
    }

    if (count_zeros > n - (last_nonzero + 1) + first_nonzero) {
        // There are some zeros within the non-zeros range - cannot proceed
        // printf("too many zeros (%d > %d)\n", count_zeros, n - (last_nonzero + 1) + first_nonzero);
        return false;
    }

    int credit = 2 * times_chosen[first_nonzero];
    state_t state = state_t::none_found;

    // printf("Initial credit is %d\n", credit);

    for (int i = first_nonzero + 1; i <= last_nonzero; i++) {
        credit = 2 * times_chosen[i] - credit;
        // printf("a[%d] is %d, credit is now %d\n", i, times_chosen[i], credit);
        if (credit == 0) {
            if (state == state_t::none_found) {
                if (i == last_nonzero) {
                    // printf("  at the end - returning true\n");
                    return true;
                }
                // The previous vertex was most likely a sink/source
                // printf("  transitioning to one_found, increasing credit by 1\n");
                state = state_t::one_found;
                credit += 1;
            } else {
                // printf("  returning false 1\n");
                return false;
            }
        } else if (credit == -1) {
            if (state == state_t::one_found) {
                // printf("  transitioning to both_found, increasing credit by 1\n");
                state = state_t::both_found;
                credit += 1;
            } else {
                // printf("  returning false 3\n");
                return false;
            }
        } else if (credit == -2) {
            if (state == state_t::none_found) {
                // printf("  transitioning to both_found, increasing credit by 2\n");
                state = state_t::both_found;
                credit += 2;
            } else {
                // printf("  returning false 4\n");
                return false;
            }
        } else if (credit < -2) {
            // printf("  returning false 5\n");
            return false;
        }
    }

    switch (state) {
    case state_t::none_found:
        // printf("  is %d zero or two?\n", credit);
        return credit == 0 || credit == 2;
    case state_t::one_found:
        // ???
        // printf("  is %d one?\n", credit);
        return credit == 1;
    case state_t::both_found:
        // printf("  is %d zero?\n", credit);
        return credit == 0;
    }
}

int main() {
    int t;
    scanf("%d\n", &t);

    while (t --> 0) {
        puts(do_single_case() ? "TAK" : "NIE");
    }

    return 0;
}