#include <cstdlib> #include <bitset> #include <functional> #include <utility> #include <chrono> #include <tuple> #include <new> #include <memory> #include <climits> #include <cfloat> #include <cinttypes> #include <exception> #include <string> #include <array> #include <vector> #include <deque> #include <list> #include <forward_list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <valarray> #include <ios> #include <istream> #include <ostream> #include <iostream> #include <fstream> #include <streambuf> #include <cstdio> #include <thread> // #include <bits/stdc++.h> using namespace std; int q; int n, wartosci[1000005]; int zmiana; int pierwsza_wart, ostatnia_wart; bool czy_same_jedynki() { bool czy_byly_jedynki = 0; for (int i = 1; i <= n; i++) { if (wartosci[i] > 1) return 0; if (wartosci[i] == 1 && czy_byly_jedynki == 1) return 0; if (wartosci[i] == 0 && wartosci[i - 1] == 1) czy_byly_jedynki = 1; } return 1; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> q; while (q--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> wartosci[i]; } pierwsza_wart = ostatnia_wart = 0; for (int i = 1; i <= n; i++) { if (wartosci[i] != 0) ostatnia_wart = i; if (wartosci[i] != 0 && pierwsza_wart == 0) pierwsza_wart = i; } for (int i = pierwsza_wart; i <= n - 1; i++) { if (wartosci[i] >= 1 && wartosci[i] < wartosci[i + 1]) { zmiana = wartosci[i]; wartosci[i] -= zmiana; wartosci[i + 1] -= zmiana; } else break; } for (int i = ostatnia_wart; i >= 2; i--) { if (wartosci[i] >= 1 && wartosci[i] < wartosci[i - 1]) { zmiana = wartosci[i]; wartosci[i] -= zmiana; wartosci[i - 1] -= zmiana; } else break; } for (int i = 1; i <= n - 1; i++) { zmiana = max(0, min(wartosci[i] - 1, wartosci[i + 1] - 1)); wartosci[i] -= zmiana; wartosci[i + 1] -= zmiana; } if (czy_same_jedynki()) cout << "TAK\n"; else cout << "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 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 | #include <cstdlib> #include <bitset> #include <functional> #include <utility> #include <chrono> #include <tuple> #include <new> #include <memory> #include <climits> #include <cfloat> #include <cinttypes> #include <exception> #include <string> #include <array> #include <vector> #include <deque> #include <list> #include <forward_list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <valarray> #include <ios> #include <istream> #include <ostream> #include <iostream> #include <fstream> #include <streambuf> #include <cstdio> #include <thread> // #include <bits/stdc++.h> using namespace std; int q; int n, wartosci[1000005]; int zmiana; int pierwsza_wart, ostatnia_wart; bool czy_same_jedynki() { bool czy_byly_jedynki = 0; for (int i = 1; i <= n; i++) { if (wartosci[i] > 1) return 0; if (wartosci[i] == 1 && czy_byly_jedynki == 1) return 0; if (wartosci[i] == 0 && wartosci[i - 1] == 1) czy_byly_jedynki = 1; } return 1; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> q; while (q--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> wartosci[i]; } pierwsza_wart = ostatnia_wart = 0; for (int i = 1; i <= n; i++) { if (wartosci[i] != 0) ostatnia_wart = i; if (wartosci[i] != 0 && pierwsza_wart == 0) pierwsza_wart = i; } for (int i = pierwsza_wart; i <= n - 1; i++) { if (wartosci[i] >= 1 && wartosci[i] < wartosci[i + 1]) { zmiana = wartosci[i]; wartosci[i] -= zmiana; wartosci[i + 1] -= zmiana; } else break; } for (int i = ostatnia_wart; i >= 2; i--) { if (wartosci[i] >= 1 && wartosci[i] < wartosci[i - 1]) { zmiana = wartosci[i]; wartosci[i] -= zmiana; wartosci[i - 1] -= zmiana; } else break; } for (int i = 1; i <= n - 1; i++) { zmiana = max(0, min(wartosci[i] - 1, wartosci[i + 1] - 1)); wartosci[i] -= zmiana; wartosci[i + 1] -= zmiana; } if (czy_same_jedynki()) cout << "TAK\n"; else cout << "NIE\n"; } } |