#include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; void solve(){ int n; cin>>n; deque<ll> q(n); for(int i=0; i<n; i++){ cin>>q[i]; } while(q.size() && !q.front()) q.pop_front(); while(q.size() && !q.back()) q.pop_back(); n = q.size(); if(n <= 1){ if(!n || q[0] == 1){ cout<<"TAK"<<nl; }else{ cout<<"NIE"<<nl; } return; } vector<ll> indeg(n-1), outdeg(n-1); int p = -1, k = -1; indeg[0] = outdeg[0] = q[0]; for(int i=1; i<n-1; i++){ indeg[i] = q[i] - outdeg[i-1]; outdeg[i] = q[i] - indeg[i-1]; if(indeg[i] < -1 || outdeg[i] < 0){ cout<<"NIE"<<nl; return; } if(outdeg[i] == 0){ if(p != -1){ cout<<"NIE"<<nl; return; } p = i-1; //cerr<<"P: "<<p<<nl; indeg[i-1]--; outdeg[i]++; } if(indeg[i] == -1){ //cerr<<"AAAAAAA"<<nl; assert(0); } } if(p == -1 && indeg[n-2] == q[n-1]+1){ p = n-2; //cerr<<"P: "<<p<<nl; indeg[n-2]--; } if(p == -1 && outdeg[n-2] == q[n-1]-1){ p = n-1; //cerr<<"P: "<<p<<nl; outdeg[n-2]++; } if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]+1){ k = n-2; //cerr<<"K: "<<k<<nl; outdeg[n-2]--; cout<<"TAK"<<nl; return; } if(indeg[n-2] == q[n-1]-1 && outdeg[n-2] == q[n-1]){ k = n-1; //cerr<<"K: "<<k<<nl; indeg[n-2]++; cout<<"TAK"<<nl; return; } if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]){ cout<<"TAK"<<nl; }else{ cout<<"NIE"<<nl; } } int main(){ cin.tie(0)->sync_with_stdio(0); int t; cin>>t; while(t--){ solve(); } return 0; }
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 | #include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; void solve(){ int n; cin>>n; deque<ll> q(n); for(int i=0; i<n; i++){ cin>>q[i]; } while(q.size() && !q.front()) q.pop_front(); while(q.size() && !q.back()) q.pop_back(); n = q.size(); if(n <= 1){ if(!n || q[0] == 1){ cout<<"TAK"<<nl; }else{ cout<<"NIE"<<nl; } return; } vector<ll> indeg(n-1), outdeg(n-1); int p = -1, k = -1; indeg[0] = outdeg[0] = q[0]; for(int i=1; i<n-1; i++){ indeg[i] = q[i] - outdeg[i-1]; outdeg[i] = q[i] - indeg[i-1]; if(indeg[i] < -1 || outdeg[i] < 0){ cout<<"NIE"<<nl; return; } if(outdeg[i] == 0){ if(p != -1){ cout<<"NIE"<<nl; return; } p = i-1; //cerr<<"P: "<<p<<nl; indeg[i-1]--; outdeg[i]++; } if(indeg[i] == -1){ //cerr<<"AAAAAAA"<<nl; assert(0); } } if(p == -1 && indeg[n-2] == q[n-1]+1){ p = n-2; //cerr<<"P: "<<p<<nl; indeg[n-2]--; } if(p == -1 && outdeg[n-2] == q[n-1]-1){ p = n-1; //cerr<<"P: "<<p<<nl; outdeg[n-2]++; } if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]+1){ k = n-2; //cerr<<"K: "<<k<<nl; outdeg[n-2]--; cout<<"TAK"<<nl; return; } if(indeg[n-2] == q[n-1]-1 && outdeg[n-2] == q[n-1]){ k = n-1; //cerr<<"K: "<<k<<nl; indeg[n-2]++; cout<<"TAK"<<nl; return; } if(indeg[n-2] == q[n-1] && outdeg[n-2] == q[n-1]){ cout<<"TAK"<<nl; }else{ cout<<"NIE"<<nl; } } int main(){ cin.tie(0)->sync_with_stdio(0); int t; cin>>t; while(t--){ solve(); } return 0; } |