#include <cstdio> #include <vector> #include <algorithm> using namespace std; bool canComeFromCountingRhyme(const vector<int>& toys) { int n = (int)toys.size(); long long S = 0; for (int c : toys) { S += c; } if (S == 0) { return true; } int L = 0; while (L < n && toys[L] == 0) { L++; } int R = n - 1; while (R >= 0 && toys[R] == 0) { R--; } if (L == R) return toys[L] == 1; if (L == R - 1) return abs(toys[L] - toys[R]) < 2; if (toys[L] > toys[L+1] || toys[R] > toys[R - 1]) return false; for (int i = L; i <= R; i++) { if (toys[i] == 0) { return false; } } long long halfS = (S + 1) / 2; for (int i = 0; i < n; i++) { if (toys[i] > halfS) { return false; } } long long evenCount = 0, oddCount = 0; for (int i = 0; i < n; i++) { if (i % 2 == 0) { evenCount += toys[i]; } else { oddCount += toys[i]; } } if (S % 2 == 0) { if (evenCount != oddCount) { return false; } } else { if (llabs(evenCount - oddCount) != 1) { return false; } } if (S > 1) { if (evenCount == 0 || oddCount == 0) { return false; } } return true; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); vector<int> heights(n); for (int i = 0; i < n; ++i) scanf("%d", &heights[i]); printf(canComeFromCountingRhyme(heights)? "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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; bool canComeFromCountingRhyme(const vector<int>& toys) { int n = (int)toys.size(); long long S = 0; for (int c : toys) { S += c; } if (S == 0) { return true; } int L = 0; while (L < n && toys[L] == 0) { L++; } int R = n - 1; while (R >= 0 && toys[R] == 0) { R--; } if (L == R) return toys[L] == 1; if (L == R - 1) return abs(toys[L] - toys[R]) < 2; if (toys[L] > toys[L+1] || toys[R] > toys[R - 1]) return false; for (int i = L; i <= R; i++) { if (toys[i] == 0) { return false; } } long long halfS = (S + 1) / 2; for (int i = 0; i < n; i++) { if (toys[i] > halfS) { return false; } } long long evenCount = 0, oddCount = 0; for (int i = 0; i < n; i++) { if (i % 2 == 0) { evenCount += toys[i]; } else { oddCount += toys[i]; } } if (S % 2 == 0) { if (evenCount != oddCount) { return false; } } else { if (llabs(evenCount - oddCount) != 1) { return false; } } if (S > 1) { if (evenCount == 0 || oddCount == 0) { return false; } } return true; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); vector<int> heights(n); for (int i = 0; i < n; ++i) scanf("%d", &heights[i]); printf(canComeFromCountingRhyme(heights)? "TAK\n" : "NIE\n"); } } |