#include <bits/stdc++.h> using namespace std; bool solve(vector<int> a) { int n = a.size(); for (int i = 1; i < n; i++) { int k = min(a[i] - 1, a[i - 1] - 1); a[i - 1] -= k; a[i] -= k; } for (auto& x : a) x -= 1; return count(a.begin(), a.end(), 0) == n; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (auto& x : a) cin >> x; while (a.back() == 0) a.pop_back(); reverse(a.begin(), a.end()); while (a.back() == 0) a.pop_back(); reverse(a.begin(), a.end()); n = a.size(); if (count(a.begin(), a.end(), 0)) { cout << "NIE\n"; continue; } if (n == 1) { cout << (a[0] == 1 ? "TAK\n" : "NIE\n"); continue; } if (n == 2) { cout << (abs(a[0] - a[1]) <= 1 ? "TAK\n" : "NIE\n"); continue; } bool result = solve(a); if (a[1] > 1) { a[1]--; result |= solve(a); a[1]++; } if (a[n - 2] > 1) { a[n - 2]--; result |= solve(a); a[n - 2]++; } if (a[1] > 1 && a[n - 2] > 1) { a[1]--; a[n - 2]--; result |= solve(a); } cout << (result ? "TAK\n" : "NIE\n"); } }
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 | #include <bits/stdc++.h> using namespace std; bool solve(vector<int> a) { int n = a.size(); for (int i = 1; i < n; i++) { int k = min(a[i] - 1, a[i - 1] - 1); a[i - 1] -= k; a[i] -= k; } for (auto& x : a) x -= 1; return count(a.begin(), a.end(), 0) == n; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (auto& x : a) cin >> x; while (a.back() == 0) a.pop_back(); reverse(a.begin(), a.end()); while (a.back() == 0) a.pop_back(); reverse(a.begin(), a.end()); n = a.size(); if (count(a.begin(), a.end(), 0)) { cout << "NIE\n"; continue; } if (n == 1) { cout << (a[0] == 1 ? "TAK\n" : "NIE\n"); continue; } if (n == 2) { cout << (abs(a[0] - a[1]) <= 1 ? "TAK\n" : "NIE\n"); continue; } bool result = solve(a); if (a[1] > 1) { a[1]--; result |= solve(a); a[1]++; } if (a[n - 2] > 1) { a[n - 2]--; result |= solve(a); a[n - 2]++; } if (a[1] > 1 && a[n - 2] > 1) { a[1]--; a[n - 2]--; result |= solve(a); } cout << (result ? "TAK\n" : "NIE\n"); } } |