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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <cstdio>
#include <string>
#include <vector>
#define DEBUG false
using namespace std;


int main() {
    int t;
    scanf("%d", &t);
    for (int t_i = 0; t_i < t; ++t_i) {
        int n;
        vector<int> zabawkis;
        int total_counts = 0;
        scanf("%d", &n);
        bool nonzeros = false;
        bool nononzeros = false;
        bool gap = false;
        int first_nonzero = -1;
        int first_zero_after_nonzero = n;
        for (int i = 0; i < n; ++i) {
            int k;
            scanf("%d", &k);
            zabawkis.push_back(k);
            total_counts += k;
            if (nononzeros && k > 0) {
                gap = true;
            }
            else if (nonzeros && k == 0) {
                nononzeros = true;
                if (first_zero_after_nonzero == n) {
                    first_zero_after_nonzero = i;
                }
            }
            else if (k > 0) {
                nonzeros = true;
                if (first_nonzero == -1) {
                    first_nonzero = i;
                }
            }
        }
        if (gap) {
            if constexpr (DEBUG) printf("-- GAP!\n");
            printf("NIE\n");
            continue;
        }
        if (total_counts <= 1) {
            if constexpr (DEBUG) printf("only 1 hit in total!\n");
            printf("TAK\n");
            continue;
        }
        if (n == 1) {
            if (zabawkis[0] <= 1) {
                if constexpr (DEBUG) printf("n=1 and its ok!\n");
                printf("TAK\n");
            } else {
                if constexpr (DEBUG) printf("n=1 but too many hits!\n");
                printf("NIE\n");
            }
            continue;
        }
        int numvalues = first_zero_after_nonzero - first_nonzero;
        if (numvalues == 1) {
            if constexpr (DEBUG) printf("Only one value and it's >1\n");
            printf("NIE\n");
            continue;
        }
        if (numvalues == 2) {
            if (abs(zabawkis[first_nonzero] - zabawkis[first_nonzero+1]) <= 1) {
                if constexpr (DEBUG) printf("Two values and they're ok\n");
                printf("TAK\n");
            } else {
                if constexpr (DEBUG) printf("Two values and they're too far apart\n");
                printf("NIE\n");
            }
            continue;
        }
        if (numvalues == 3) {
            int first_red = min(zabawkis[first_nonzero], zabawkis[first_nonzero+1]) - 1;
            zabawkis[first_nonzero] -= first_red;
            zabawkis[first_nonzero+1] -= first_red;
            int second_red = min(zabawkis[first_nonzero+1], zabawkis[first_nonzero+2]) - 1;
            zabawkis[first_nonzero+1] -= second_red;
            zabawkis[first_nonzero+2] -= second_red;
            if (zabawkis[first_nonzero] != 1 || zabawkis[first_nonzero+2] != 1 || zabawkis[first_nonzero+1] > 3) {
                if constexpr (DEBUG) printf("Non-reducible 3-len query\n");
                printf("NIE\n");
            } else {
                if constexpr (DEBUG) printf("Correctly reducible 3-len query\n");
                printf("TAK\n");
            }
            continue;
        }
        // tutaj mamy już spójny podciąg co najmniej czterech dodatnich liczb

        // najpierw ścinamy brzegi. Jeśli nie zetną się do 1, no to kicha.
        int left_border_reducible = min(zabawkis[first_nonzero], zabawkis[first_nonzero+1]) - 1;
        zabawkis[first_nonzero] -= left_border_reducible;
        zabawkis[first_nonzero+1] -= left_border_reducible;
        int right_border_reducible = min(zabawkis[first_zero_after_nonzero-2], zabawkis[first_zero_after_nonzero-1]) - 1;
        zabawkis[first_zero_after_nonzero-2] -= right_border_reducible;
        zabawkis[first_zero_after_nonzero-1] -= right_border_reducible;

        if (zabawkis[first_nonzero] > 1 || zabawkis[first_zero_after_nonzero-1] > 1) {
            if constexpr (DEBUG) printf("Too many border hits\n");
            printf("NIE\n");
            continue;
        }

        if (zabawkis[first_nonzero+1] > 1) {
            if constexpr (DEBUG) printf("Trying 2atic reduction first\n");
            bool badnumber = false;
            // It is possible to go for 1 2 ... 1, let's try it
            vector<int> zabawkis2 = zabawkis;
            int first_reduction = min(zabawkis2[first_nonzero+1]-2, zabawkis2[first_nonzero+2]-1);
            if constexpr (DEBUG) printf("Reducing (%d  %d)   to   (%d  %d)\n", zabawkis2[first_nonzero+1], zabawkis2[first_nonzero+2], zabawkis2[first_nonzero+1] - first_reduction, zabawkis2[first_nonzero+2] - first_reduction);
            zabawkis2[first_nonzero+1] -= first_reduction;
            zabawkis2[first_nonzero+2] -= first_reduction;
            // zabawkis[first_nonzero+1] is now reduced to at most 2.
            // tbh we could skip this if it's 3 or more...
            if (zabawkis2[first_nonzero+1] > 2) {
                badnumber = true;
            }
            if (!badnumber) {
                for (int i = first_nonzero + 3; i < first_zero_after_nonzero; ++i) {
                    int reducible = min(zabawkis2[i-1], zabawkis2[i]) - 1;
                    if constexpr (DEBUG) printf("Reducing (%d  %d)   to   (%d  %d)\n", zabawkis2[i-1], zabawkis2[i], zabawkis2[i-1] - reducible, zabawkis2[i] - reducible);
                    zabawkis2[i-1] -= reducible;
                    zabawkis2[i] -= reducible;

                    if (zabawkis2[i-1] > 1) {
                        if (!(zabawkis2[i-1] == 2 && i == first_zero_after_nonzero - 1)) {
                            badnumber = true;
                            break;
                        }
                    }
                }
            }
            if constexpr (DEBUG) {
                printf("After 2atic reduction:\n");
                for (int i = first_nonzero; i < first_zero_after_nonzero; ++i) {
                    printf("%d ", zabawkis2[i]);
                }
                printf("\n");
            }
            if (!badnumber) {
                if constexpr (DEBUG) printf("2atic reduction solution is correct!\n");
                printf("TAK\n");
                continue;
            }

            if constexpr (DEBUG) printf("2atic reduction solution incorrect.\n");
        }


        if constexpr (DEBUG) printf("Trying regular reduction\n");
        bool badnumber = false;
        // TRIAL 1: go for 1 1 1 ... 1 1 1, or 1 1 1 ... 1 2 1
        for (int i = first_nonzero + 1; i < first_zero_after_nonzero; ++i) {
            int reducible = min(zabawkis[i-1], zabawkis[i]) - 1; // -1 bo nie redukujemy do zera
            if constexpr (DEBUG) printf("Reducing (%d  %d)   to   (%d  %d)\n", zabawkis[i-1], zabawkis[i], zabawkis[i-1] - reducible, zabawkis[i] - reducible);
            zabawkis[i-1] -= reducible;
            zabawkis[i] -= reducible;

            if (zabawkis[i-1] > 1) {
                if (!(zabawkis[i-1] == 2 && i == first_zero_after_nonzero - 1)) {
                    badnumber = true;
                    break;
                }
            }
        }
        if constexpr (DEBUG) {
            printf("After reduction:\n");
            for (int i = first_nonzero; i < first_zero_after_nonzero; ++i) {
                printf("%d ", zabawkis[i]);
            }
            printf("\n");
        }
        if (badnumber) {
            printf("NIE\n");
        } else {
            printf("TAK\n");
        }
        if constexpr (DEBUG) printf("=================================================\n");
    }
    return 0;
}