#include <bits/stdc++.h> using namespace std; typedef vector<int> VI; typedef pair <int,int> ii; typedef long long LL; typedef pair <LL,LL> pll; #define pb push_back const int INF = 2147483647; const int N = 1000005; int tab[N], z, i, n, bat[N], ok, jed, u, st; LL s[2]; VI v; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> z; while (z--) { cin >> n; s[0] = s[1] = 0; for (i=0;i<n;i++) { cin >> tab[i]; s[i % 2] += tab[i]; } if (n == 1) { if (tab[0] != 1) cout << "NIE\n"; else cout << "TAK\n"; continue; } i = 0; while (tab[i] == 0) i++; while (i < n && tab[i] != 0) i++; while (i < n && tab[i] == 0) i++; if (i < n) { cout << "NIE\n"; continue; } if (s[0] + s[1] == 1) { cout << "TAK\n"; continue; } if (max(s[0], s[1]) - min(s[0], s[1]) > 1) { cout << "NIE\n"; continue; } v.clear(); ok = 1; for (i=0;i<n;i++) { if (tab[i] == 0) continue; u = (i == 0 ? 0 : tab[i - 1]) + (i == n - 1 ? 0 : tab[i + 1]); if (tab[i] == u) v.pb(i); else if (tab[i] == u + 1) { v.pb(i); v.pb(i); } else if (tab[i] > u + 1) ok = 0; } if (v.size() > 2) ok = 0; else if (v.size() == 2) { if (s[0] > s[1] && (v[0] % 2 != 0 || v[1] % 2 != 0)) ok = 0; if (s[1] > s[0] && (v[0] % 2 != 1 || v[1] % 2 != 1)) ok = 0; if (s[1] == s[0] && v[0] % 2 == v[1] % 2) ok = 0; } else if (v.size() == 1) { if (s[0] > s[1] && v[0] % 2 == 1) ok = 0; if (s[1] > s[0] && v[0] % 2 == 0) ok = 0; } if (!ok) cout << "NIE\n"; else cout << "TAK\n"; } 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 | #include <bits/stdc++.h> using namespace std; typedef vector<int> VI; typedef pair <int,int> ii; typedef long long LL; typedef pair <LL,LL> pll; #define pb push_back const int INF = 2147483647; const int N = 1000005; int tab[N], z, i, n, bat[N], ok, jed, u, st; LL s[2]; VI v; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> z; while (z--) { cin >> n; s[0] = s[1] = 0; for (i=0;i<n;i++) { cin >> tab[i]; s[i % 2] += tab[i]; } if (n == 1) { if (tab[0] != 1) cout << "NIE\n"; else cout << "TAK\n"; continue; } i = 0; while (tab[i] == 0) i++; while (i < n && tab[i] != 0) i++; while (i < n && tab[i] == 0) i++; if (i < n) { cout << "NIE\n"; continue; } if (s[0] + s[1] == 1) { cout << "TAK\n"; continue; } if (max(s[0], s[1]) - min(s[0], s[1]) > 1) { cout << "NIE\n"; continue; } v.clear(); ok = 1; for (i=0;i<n;i++) { if (tab[i] == 0) continue; u = (i == 0 ? 0 : tab[i - 1]) + (i == n - 1 ? 0 : tab[i + 1]); if (tab[i] == u) v.pb(i); else if (tab[i] == u + 1) { v.pb(i); v.pb(i); } else if (tab[i] > u + 1) ok = 0; } if (v.size() > 2) ok = 0; else if (v.size() == 2) { if (s[0] > s[1] && (v[0] % 2 != 0 || v[1] % 2 != 0)) ok = 0; if (s[1] > s[0] && (v[0] % 2 != 1 || v[1] % 2 != 1)) ok = 0; if (s[1] == s[0] && v[0] % 2 == v[1] % 2) ok = 0; } else if (v.size() == 1) { if (s[0] > s[1] && v[0] % 2 == 1) ok = 0; if (s[1] > s[0] && v[0] % 2 == 0) ok = 0; } if (!ok) cout << "NIE\n"; else cout << "TAK\n"; } return 0; } |