#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 305; const LL INF = 10000000000000LL; int n; LL increase[MAXN]; vector<LL> gen_sequence(int len) { vector<LL> pref_sums; pref_sums.push_back(0); for (int i = 1; i <= len; i++) { pref_sums.push_back(INF); for (int j = 1; i-j >= 0; j++) pref_sums[i] = min(pref_sums[i], pref_sums[i-j] + increase[j]); } vector<LL> seq; for (int i = 0; i < len; i++) seq.push_back(pref_sums[i+1] - pref_sums[i]); while (seq.size() <= n+1) seq.push_back(-INF); return seq; } bool check_correctness(const vector<LL>& solution) { vector<LL> pref_sum; pref_sum.push_back(0); for (LL elem : solution) pref_sum.push_back(pref_sum.back() + elem); for (int i = 1; i <= n; i++) { bool was_increase = false; for (int j = 0; j+i-1 < solution.size(); j++) { if (pref_sum[j+i] - pref_sum[j] > increase[i]) return false; if (pref_sum[j+i] - pref_sum[j] == increase[i]) was_increase = true; } if (!was_increase) return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> increase[i]; vector<LL> sequence; for (int i = 1; i <= n; i++) { vector<LL> s = gen_sequence(i); sequence.insert(sequence.end(), s.begin(), s.end()); } if (!check_correctness(sequence)) { cout << "NIE\n"; return 0; } cout << "TAK\n"; cout << sequence.size() << "\n"; for (LL elem : sequence) cout << elem << " "; cout << "\n"; return 0; }
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; typedef long long int LL; const int MAXN = 305; const LL INF = 10000000000000LL; int n; LL increase[MAXN]; vector<LL> gen_sequence(int len) { vector<LL> pref_sums; pref_sums.push_back(0); for (int i = 1; i <= len; i++) { pref_sums.push_back(INF); for (int j = 1; i-j >= 0; j++) pref_sums[i] = min(pref_sums[i], pref_sums[i-j] + increase[j]); } vector<LL> seq; for (int i = 0; i < len; i++) seq.push_back(pref_sums[i+1] - pref_sums[i]); while (seq.size() <= n+1) seq.push_back(-INF); return seq; } bool check_correctness(const vector<LL>& solution) { vector<LL> pref_sum; pref_sum.push_back(0); for (LL elem : solution) pref_sum.push_back(pref_sum.back() + elem); for (int i = 1; i <= n; i++) { bool was_increase = false; for (int j = 0; j+i-1 < solution.size(); j++) { if (pref_sum[j+i] - pref_sum[j] > increase[i]) return false; if (pref_sum[j+i] - pref_sum[j] == increase[i]) was_increase = true; } if (!was_increase) return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> increase[i]; vector<LL> sequence; for (int i = 1; i <= n; i++) { vector<LL> s = gen_sequence(i); sequence.insert(sequence.end(), s.begin(), s.end()); } if (!check_correctness(sequence)) { cout << "NIE\n"; return 0; } cout << "TAK\n"; cout << sequence.size() << "\n"; for (LL elem : sequence) cout << elem << " "; cout << "\n"; return 0; } |