#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=1e6+5; int n; ll a[N],b[N]; int mn,mx; bool test(){ int rem=0; for(int i=mn; i<=mx ;i++){ if(a[i]<0) return false; rem=a[i]-rem; if(rem<0) return false; } if(rem!=0) return false; return true; } void solve(){ cin >> n; mn=n+1,mx=0; for(int i=1; i<=n ;i++){ cin >> a[i]; if(a[i]>0){ mn=min(mn,i); mx=max(mx,i); } } ll s=0; for(int i=mn; i<=mx ;i++){ if(a[i]==0){ cout << "NIE\n";return; } a[i]--; s=(s+a[i])%2; } if(s==1){ if(n==1){ cout << "NIE\n";return; } a[mn+1]--; if(test()){ cout << "TAK\n";return; } a[mn+1]++; a[mx-1]--; if(test()){ cout << "TAK\n";return; } a[mx+1]++; } else{ if(test()){ cout << "TAK\n";return; } if(n==1){ cout << "NIE\n";return; } a[mn+1]--; a[mx-1]--; if(test()){ cout << "TAK\n";return; } } cout << "NIE\n"; } int main(){ ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t;while(t--) solve(); }
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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second const int N=1e6+5; int n; ll a[N],b[N]; int mn,mx; bool test(){ int rem=0; for(int i=mn; i<=mx ;i++){ if(a[i]<0) return false; rem=a[i]-rem; if(rem<0) return false; } if(rem!=0) return false; return true; } void solve(){ cin >> n; mn=n+1,mx=0; for(int i=1; i<=n ;i++){ cin >> a[i]; if(a[i]>0){ mn=min(mn,i); mx=max(mx,i); } } ll s=0; for(int i=mn; i<=mx ;i++){ if(a[i]==0){ cout << "NIE\n";return; } a[i]--; s=(s+a[i])%2; } if(s==1){ if(n==1){ cout << "NIE\n";return; } a[mn+1]--; if(test()){ cout << "TAK\n";return; } a[mn+1]++; a[mx-1]--; if(test()){ cout << "TAK\n";return; } a[mx+1]++; } else{ if(test()){ cout << "TAK\n";return; } if(n==1){ cout << "NIE\n";return; } a[mn+1]--; a[mx-1]--; if(test()){ cout << "TAK\n";return; } } cout << "NIE\n"; } int main(){ ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t;while(t--) solve(); } |