#include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef uint64_t ull; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; constexpr ll LINF = 1e18; constexpr int INF = 1e9; bool is_solved(vi &a, int n) { for (int i = 0; i < n; ++i) { if (a[i]) { return false; } } return true; } bool solve(vi &a, int n, bool reduce_by_one = false) { int pos = 0; while (a[pos] == 0) { ++pos; } int start = pos; --a[pos]; if (reduce_by_one) { int new_pos = pos + 1; while (new_pos < n && a[new_pos] != 0) { --a[new_pos]; ++new_pos; } start = new_pos - 1; } while (true) { int reduction = min(a[pos], a[pos + 1] - 1); if (reduction == -1) { break; } a[pos] -= reduction; a[pos + 1] -= reduction + 1; pos += 1; } // step back if (pos > 0 && a[pos - 1] >= 1) { --a[pos - 1]; } // step from start if (start + 1 < n && a[start + 1] == 1) { --a[start + 1]; } else if (start > 0 && a[start - 1] == 1) { --a[start - 1]; } return is_solved(a, n); } bool solve_cases(vi &a, vi &b, int n) { if (solve(b, n, false)) { return true; } // Reduced by one for (int i = 0; i < n; ++i) { b[i] = a[i]; } b[n] = 0; if (solve(b, n, true)) { return true; } // Reversed for (int i = 0; i < n; ++i) { b[i] = a[n - i - 1]; } b[n] = 0; if (solve(b, n)) { return true; } // Reversed, reduced by 1 for (int i = 0; i < n; ++i) { b[i] = a[n - i - 1]; } b[n] = 0; if (solve(b, n, true)) { return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t, n; cin >> t; vi a(1000002); vi b(1000002); while (t--) { cin >> n; a[n] = 0; b[n] = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; b[i] = a[i]; } cout << (solve_cases(a, b, n) ? "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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | #include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef uint64_t ull; typedef unsigned int ui; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<long long> vll; constexpr ll LINF = 1e18; constexpr int INF = 1e9; bool is_solved(vi &a, int n) { for (int i = 0; i < n; ++i) { if (a[i]) { return false; } } return true; } bool solve(vi &a, int n, bool reduce_by_one = false) { int pos = 0; while (a[pos] == 0) { ++pos; } int start = pos; --a[pos]; if (reduce_by_one) { int new_pos = pos + 1; while (new_pos < n && a[new_pos] != 0) { --a[new_pos]; ++new_pos; } start = new_pos - 1; } while (true) { int reduction = min(a[pos], a[pos + 1] - 1); if (reduction == -1) { break; } a[pos] -= reduction; a[pos + 1] -= reduction + 1; pos += 1; } // step back if (pos > 0 && a[pos - 1] >= 1) { --a[pos - 1]; } // step from start if (start + 1 < n && a[start + 1] == 1) { --a[start + 1]; } else if (start > 0 && a[start - 1] == 1) { --a[start - 1]; } return is_solved(a, n); } bool solve_cases(vi &a, vi &b, int n) { if (solve(b, n, false)) { return true; } // Reduced by one for (int i = 0; i < n; ++i) { b[i] = a[i]; } b[n] = 0; if (solve(b, n, true)) { return true; } // Reversed for (int i = 0; i < n; ++i) { b[i] = a[n - i - 1]; } b[n] = 0; if (solve(b, n)) { return true; } // Reversed, reduced by 1 for (int i = 0; i < n; ++i) { b[i] = a[n - i - 1]; } b[n] = 0; if (solve(b, n, true)) { return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t, n; cin >> t; vi a(1000002); vi b(1000002); while (t--) { cin >> n; a[n] = 0; b[n] = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; b[i] = a[i]; } cout << (solve_cases(a, b, n) ? "TAK" : "NIE") << '\n'; } return 0; } |