#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<ll> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } if(n == 1) { cout << (a[0] == 1 ? "TAK" : "NIE") << "\n"; continue; } int L = 0, R = n - 1; while(L < n && a[L] == 0) { L++; } while(R >= 0 && a[R] == 0) { R--; } int m = R - L + 1; vector<ll> B(m), F(m); for(int i = 0; i < m; i++) { B[i] = a[L + i]; } F[0] = B[0]; for(int i = 1; i < m; i++) { F[i] = B[i] - F[i - 1]; } ll kand = F[m - 1]; if(kand != 1 && kand != -1) { cout << "NIE" << "\n"; continue; } bool ok = false; for(int r = 0; r < m; r++) { int d = m - 1 - r; if(kand == 1 && (d % 2 != 0)) { continue; } if(kand == -1 && (d % 2 == 0)) { continue; } bool k = true; for(int i = 0; i < r; i++) { if(F[i] <= 0) { k = false; break; } } if(!k) continue; for(int i = r; i < m - 1; i++) { int d = i - r; if(d % 2 == 0) { if(F[i] <= 1) { k = false; break; } } else { if(F[i] < 0) { k = false; break; } } } int w = (d % 2 == 0) ? 1 : -1; if(F[m - 1] != w) k = false; if(k) { ok = true; break; } } cout << (ok ? "TAK" : "NIE") << "\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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<ll> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } if(n == 1) { cout << (a[0] == 1 ? "TAK" : "NIE") << "\n"; continue; } int L = 0, R = n - 1; while(L < n && a[L] == 0) { L++; } while(R >= 0 && a[R] == 0) { R--; } int m = R - L + 1; vector<ll> B(m), F(m); for(int i = 0; i < m; i++) { B[i] = a[L + i]; } F[0] = B[0]; for(int i = 1; i < m; i++) { F[i] = B[i] - F[i - 1]; } ll kand = F[m - 1]; if(kand != 1 && kand != -1) { cout << "NIE" << "\n"; continue; } bool ok = false; for(int r = 0; r < m; r++) { int d = m - 1 - r; if(kand == 1 && (d % 2 != 0)) { continue; } if(kand == -1 && (d % 2 == 0)) { continue; } bool k = true; for(int i = 0; i < r; i++) { if(F[i] <= 0) { k = false; break; } } if(!k) continue; for(int i = r; i < m - 1; i++) { int d = i - r; if(d % 2 == 0) { if(F[i] <= 1) { k = false; break; } } else { if(F[i] < 0) { k = false; break; } } } int w = (d % 2 == 0) ? 1 : -1; if(F[m - 1] != w) k = false; if(k) { ok = true; break; } } cout << (ok ? "TAK" : "NIE") << "\n"; } return 0; } |