#include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; int main() { #ifdef iq freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; vector <pair <ll, ll> > x, y; for (int i = 0; i < n; i++) { ll l, a, b; cin >> l >> a >> b; x.push_back({a, l}); y.push_back({b, l}); } sort(x.rbegin(), x.rend()); sort(y.rbegin(), y.rend()); int i = 0, j = 0; ll s = 0; bool bad = false; while (i < (int) x.size() && j < (int) y.size()) { if (!x[i].second) { i++; continue; } if (!y[j].second) { j++; continue; } ll mn = min(x[i].second, y[j].second); x[i].second -= mn, y[j].second -= mn; s += x[i].first * mn - y[j].first * mn; if (s < 0) { bad = true; } } if (s) bad = true; if (bad) cout << "NIE\n"; else cout << "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 | #include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <bitset> #include <sstream> #include <chrono> #include <cstring> using namespace std; typedef long long ll; int main() { #ifdef iq freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; vector <pair <ll, ll> > x, y; for (int i = 0; i < n; i++) { ll l, a, b; cin >> l >> a >> b; x.push_back({a, l}); y.push_back({b, l}); } sort(x.rbegin(), x.rend()); sort(y.rbegin(), y.rend()); int i = 0, j = 0; ll s = 0; bool bad = false; while (i < (int) x.size() && j < (int) y.size()) { if (!x[i].second) { i++; continue; } if (!y[j].second) { j++; continue; } ll mn = min(x[i].second, y[j].second); x[i].second -= mn, y[j].second -= mn; s += x[i].first * mn - y[j].first * mn; if (s < 0) { bad = true; } } if (s) bad = true; if (bad) cout << "NIE\n"; else cout << "TAK\n"; } } |