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
  #include <iostream>
  #include <stdio.h>
  #include <cstdio>
  #include <vector>
  #include <algorithm>
  using namespace std;

  int points[1000000];

  void print(int* array, int length) {
    return;
  }
  
  bool solveOnce() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> points[i];
    }
    
    //check integrity
    int index = 0;
    while (points[index] == 0) {
      index++;
    }
    int left = index;
    while (points[index] != 0 && index < n) {
      index++;
    }
    int right = index - 1;
    while (points[index] == 0 && index < n) {
      index++;
    }
    if (index != n) {
      return false;
    }

    // remove floor
    for (int i = left; i <= right; i++) {
      points[i]--;
    }

    // greedy left
    while (true) {
      int above = points[left];
      int aside = points[left + 1];
      if (above >= aside) {
        points[left] -= aside;
        points[left + 1] -= aside;
        break;
      }
      points[left] -= above;
      points[left + 1] -= (above + 1);
      left++;
    }
    
    // greedy right
    while(true) {
      int above = points[right];
      int aside = points[right - 1];
      if (above >= aside) {
        points[right] -= aside;
        points[right - 1] -= aside;
        break;
      }
      points[right] -= above;
      points[right - 1] -= (above + 1);
      right--;
    }

    // remove islands
    for (int i = left; i <= right; i++) {
      int common = min(points[i], points[i + 1]);
      points[i] -= common;
      points[i + 1] -= common;
    }
    
    // expect empty
    for (int i = 0; i < n; i++) {
      if (points[i] > 0) {
        return false;
      }
    }
    return true;
  }

  int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
      bool possible = solveOnce();
      if (possible) {
        cout << "TAK\n";
      } else {
        cout << "NIE\n";
      }
    }
    return 0;
  }