#include <cstdio> #include <vector> #define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i) using namespace std; int z, n; int first_pos, last_pos; bool error; int main() { scanf("%d", &z); while(z--) { scanf("%d", &n); vector<int> A(n); FOR(i,0,n) scanf("%d", &A[i]); // Rule 1 - no gaps inside first_pos = -1; last_pos = -1; FOR(i,0,n) { if (A[i] != 0) { if (first_pos == -1) first_pos = i; last_pos = i; } } error = false; FOR(i,first_pos,last_pos+1) { if (A[i] == 0) { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 2 - length 1 if (first_pos == last_pos) { if (A[first_pos] == 1) printf("TAK\n"); else printf("NIE\n"); continue; } // Rule 3 - odd and even sum should be in [-1, 0, 1] signed long long int S = 0; FOR(i,first_pos,last_pos+1) if (i&1) S += A[i]; else S -= A[i]; if (S != -1 && S != 0 && S != 1) { printf("NIE\n"); continue; } // Rule 4 - No regress at the beginning and end if (last_pos - first_pos + 1 > 2) { if (A[first_pos] > A[first_pos+1]) { printf("NIE\n"); continue; } if (A[last_pos] > A[last_pos-1]) { printf("NIE\n"); continue; } } // Rule 5 - no "hop" inside if (last_pos - first_pos + 1 > 3) { error = false; FOR(i,first_pos+1, last_pos) { if (A[i] > A[i-1] + A[i+1]) { error = true; break; } } if (error) { printf("NIE\n"); continue; } } // Rule 6a - cut from left error = false; while (last_pos - first_pos + 1 > 2) { if (A[first_pos] == A[first_pos+1]) { A[first_pos+1] = 1; A[first_pos] = 1; break; } else if (A[first_pos] < A[first_pos+1]) { A[first_pos+1] -= A[first_pos]; A[first_pos] = 0; ++first_pos; } else { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 6b - cut from right error = false; while (last_pos - first_pos + 1 > 2) { if (A[last_pos] == A[last_pos-1]) { A[last_pos-1] = 1; A[last_pos] = 1; break; } else if (A[last_pos] < A[last_pos-1]) { A[last_pos-1] -= A[last_pos]; A[last_pos] = 0; --last_pos; } else { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 6c if (last_pos - first_pos + 1 == 2) { int diff = A[first_pos] - A[last_pos]; if (diff == -1 || diff == 0 || diff == 1) printf("TAK\n"); else printf("NIE\n"); continue; } // Rule 6d if (last_pos - first_pos + 1 <= 4) { error = false; FOR(i,first_pos,last_pos+1) if (A[i] != 1) { error = true; break; } if (error) printf("NIE\n"); else printf("TAK\n"); continue; } // Rule 7 - check if A can be ZIG-ZAG first_pos += 2; last_pos -= 2; error = false; FOR(i,first_pos,last_pos) { if (A[i+1] <= A[i]-1) { error = true; break; } A[i+1] = A[i+1] - A[i] + 1; A[i] = 0; ++first_pos; } if (error || A[last_pos] != 1) { printf("NIE\n"); continue; } printf("TAK\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 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 126 127 128 129 | #include <cstdio> #include <vector> #define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i) using namespace std; int z, n; int first_pos, last_pos; bool error; int main() { scanf("%d", &z); while(z--) { scanf("%d", &n); vector<int> A(n); FOR(i,0,n) scanf("%d", &A[i]); // Rule 1 - no gaps inside first_pos = -1; last_pos = -1; FOR(i,0,n) { if (A[i] != 0) { if (first_pos == -1) first_pos = i; last_pos = i; } } error = false; FOR(i,first_pos,last_pos+1) { if (A[i] == 0) { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 2 - length 1 if (first_pos == last_pos) { if (A[first_pos] == 1) printf("TAK\n"); else printf("NIE\n"); continue; } // Rule 3 - odd and even sum should be in [-1, 0, 1] signed long long int S = 0; FOR(i,first_pos,last_pos+1) if (i&1) S += A[i]; else S -= A[i]; if (S != -1 && S != 0 && S != 1) { printf("NIE\n"); continue; } // Rule 4 - No regress at the beginning and end if (last_pos - first_pos + 1 > 2) { if (A[first_pos] > A[first_pos+1]) { printf("NIE\n"); continue; } if (A[last_pos] > A[last_pos-1]) { printf("NIE\n"); continue; } } // Rule 5 - no "hop" inside if (last_pos - first_pos + 1 > 3) { error = false; FOR(i,first_pos+1, last_pos) { if (A[i] > A[i-1] + A[i+1]) { error = true; break; } } if (error) { printf("NIE\n"); continue; } } // Rule 6a - cut from left error = false; while (last_pos - first_pos + 1 > 2) { if (A[first_pos] == A[first_pos+1]) { A[first_pos+1] = 1; A[first_pos] = 1; break; } else if (A[first_pos] < A[first_pos+1]) { A[first_pos+1] -= A[first_pos]; A[first_pos] = 0; ++first_pos; } else { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 6b - cut from right error = false; while (last_pos - first_pos + 1 > 2) { if (A[last_pos] == A[last_pos-1]) { A[last_pos-1] = 1; A[last_pos] = 1; break; } else if (A[last_pos] < A[last_pos-1]) { A[last_pos-1] -= A[last_pos]; A[last_pos] = 0; --last_pos; } else { error = true; break; } } if (error) { printf("NIE\n"); continue; } // Rule 6c if (last_pos - first_pos + 1 == 2) { int diff = A[first_pos] - A[last_pos]; if (diff == -1 || diff == 0 || diff == 1) printf("TAK\n"); else printf("NIE\n"); continue; } // Rule 6d if (last_pos - first_pos + 1 <= 4) { error = false; FOR(i,first_pos,last_pos+1) if (A[i] != 1) { error = true; break; } if (error) printf("NIE\n"); else printf("TAK\n"); continue; } // Rule 7 - check if A can be ZIG-ZAG first_pos += 2; last_pos -= 2; error = false; FOR(i,first_pos,last_pos) { if (A[i+1] <= A[i]-1) { error = true; break; } A[i+1] = A[i+1] - A[i] + 1; A[i] = 0; ++first_pos; } if (error || A[last_pos] != 1) { printf("NIE\n"); continue; } printf("TAK\n"); } } |