#include <iostream> #include <vector> #include <algorithm> bool comp(int64_t a, int64_t b, int64_t c, int64_t d) { // a/b >= c/d int mult = 1; if (b<0) mult *= -1; if (d<0) mult *= -1; return mult > 0 ? a*d >= c*b : a*d <= c*b; } bool solve(bool dbg = false) { int n; std::cin >> n; int64_t e1 = 0, e2 = 0; std::vector<std::pair<int64_t, int64_t>> A,B; A.reserve(n); B.reserve(n); for (int i=0;i<n;++i) { int64_t v,t1,t2; std::cin >> v >> t1 >> t2; A.push_back({t1, v}); B.push_back({t2, v}); } std::sort(A.begin(), A.end()); std::sort(B.begin(), B.end()); int t = 0; int64_t e = 0, v = 0; bool start = true; for (const auto& p : A) { int64_t de = p.first*p.second; int64_t dv = p.second; int64_t tp = B[t].first; int64_t vp = B[t].second; while (!start && t < n && e+de >= B[t].first * (v+dv) && e <= B[t].first * v && comp((e-v*tp),(dv*tp-de),(vp - v),dv)) { e -= B[t].first*B[t].second; v -= B[t].second; ++t; tp = B[t].first; vp = B[t].second; } e += de; v += dv; start = false; } return t == n; } int main() { std::ios_base::sync_with_stdio(0); int t; std::cin >> t; while (t--) { std::cout << (solve(t == -1) ? "TAK" : "NIE") << std::endl; } 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 | #include <iostream> #include <vector> #include <algorithm> bool comp(int64_t a, int64_t b, int64_t c, int64_t d) { // a/b >= c/d int mult = 1; if (b<0) mult *= -1; if (d<0) mult *= -1; return mult > 0 ? a*d >= c*b : a*d <= c*b; } bool solve(bool dbg = false) { int n; std::cin >> n; int64_t e1 = 0, e2 = 0; std::vector<std::pair<int64_t, int64_t>> A,B; A.reserve(n); B.reserve(n); for (int i=0;i<n;++i) { int64_t v,t1,t2; std::cin >> v >> t1 >> t2; A.push_back({t1, v}); B.push_back({t2, v}); } std::sort(A.begin(), A.end()); std::sort(B.begin(), B.end()); int t = 0; int64_t e = 0, v = 0; bool start = true; for (const auto& p : A) { int64_t de = p.first*p.second; int64_t dv = p.second; int64_t tp = B[t].first; int64_t vp = B[t].second; while (!start && t < n && e+de >= B[t].first * (v+dv) && e <= B[t].first * v && comp((e-v*tp),(dv*tp-de),(vp - v),dv)) { e -= B[t].first*B[t].second; v -= B[t].second; ++t; tp = B[t].first; vp = B[t].second; } e += de; v += dv; start = false; } return t == n; } int main() { std::ios_base::sync_with_stdio(0); int t; std::cin >> t; while (t--) { std::cout << (solve(t == -1) ? "TAK" : "NIE") << std::endl; } return 0; } |