#include <bits/stdc++.h> #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; template<class T> void chkmn(T &x, T y) { if (y < x) x = y; } template<class T> void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 1000010; int n, m, a[maxn], b[maxn], f[maxn][3][3]; ll s[maxn]; bool check() { int rest = 0; rep (i, 1, n) { if (i == n && a[i] - rest != 0) return false; if (i < n && a[i] - rest <= 0) return false; rest = a[i] - rest; } return true; } bool check(int x, ll v) { if (x == n) return v == 0; return v > 0; } void work() { cin >> n, m = 0; rep (i, 1, n) cin >> a[i]; int l = 1, r = n; while (l <= n && !a[l]) l++; while (r >= 1 && !a[r]) r--; rep (i, l, r) b[++m] = a[i]; n = m; rep (i, 1, n) a[i] = b[i]; if (n == 1) return cout << (a[1] == 1 ? "TAK" : "NIE") << '\n', void(); if (check()) return cout << "TAK\n", void(); rep (i, 1, n) s[i] = a[i] - s[i - 1]; rep (i, 0, n) rep (j, 0, 2) rep (k, 0, 2) f[i][j][k] = 0; f[0][0][1] = 1; rep (i, 1, n) { rep (k, 0, 2) { if (f[i - 1][0][2 - k]) { if (check(i, s[i] + k - 1)) f[i][0][k] = 1; if (k < 2 && check(i, s[i] + k - 1 + 1)) f[i][1][k + 1] = 1; } if (f[i - 1][1][2 - k]) { if (k < 2 && check(i, s[i] + k - 1 + 1)) f[i][1][k + 1] = 1; if (check(i, s[i] + k - 1)) f[i][2][k] = 1; } if (f[i - 1][2][2 - k]) { if (check(i, s[i] + k - 1)) f[i][2][k] = 1; } } } int ok = 0; rep (i, 0, 2) rep (j, 0, 2) ok |= f[n][i][j]; cout << (ok ? "TAK" : "NIE") << '\n'; } int main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); int t; cin >> t; while (t--) work(); }
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 | #include <bits/stdc++.h> #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; template<class T> void chkmn(T &x, T y) { if (y < x) x = y; } template<class T> void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 1000010; int n, m, a[maxn], b[maxn], f[maxn][3][3]; ll s[maxn]; bool check() { int rest = 0; rep (i, 1, n) { if (i == n && a[i] - rest != 0) return false; if (i < n && a[i] - rest <= 0) return false; rest = a[i] - rest; } return true; } bool check(int x, ll v) { if (x == n) return v == 0; return v > 0; } void work() { cin >> n, m = 0; rep (i, 1, n) cin >> a[i]; int l = 1, r = n; while (l <= n && !a[l]) l++; while (r >= 1 && !a[r]) r--; rep (i, l, r) b[++m] = a[i]; n = m; rep (i, 1, n) a[i] = b[i]; if (n == 1) return cout << (a[1] == 1 ? "TAK" : "NIE") << '\n', void(); if (check()) return cout << "TAK\n", void(); rep (i, 1, n) s[i] = a[i] - s[i - 1]; rep (i, 0, n) rep (j, 0, 2) rep (k, 0, 2) f[i][j][k] = 0; f[0][0][1] = 1; rep (i, 1, n) { rep (k, 0, 2) { if (f[i - 1][0][2 - k]) { if (check(i, s[i] + k - 1)) f[i][0][k] = 1; if (k < 2 && check(i, s[i] + k - 1 + 1)) f[i][1][k + 1] = 1; } if (f[i - 1][1][2 - k]) { if (k < 2 && check(i, s[i] + k - 1 + 1)) f[i][1][k + 1] = 1; if (check(i, s[i] + k - 1)) f[i][2][k] = 1; } if (f[i - 1][2][2 - k]) { if (check(i, s[i] + k - 1)) f[i][2][k] = 1; } } } int ok = 0; rep (i, 0, 2) rep (j, 0, 2) ok |= f[n][i][j]; cout << (ok ? "TAK" : "NIE") << '\n'; } int main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); int t; cin >> t; while (t--) work(); } |