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 #include using namespace std; #define int long long main(){ ios_base::sync_with_stdio(0); cin.tie(0); int z; cin >> z; while(z--){ int n; cin >> n; int al = 0; bool ok = 1; vector l(n), a(n), b(n); vector > tar(n), h(n); int bal1 = 0, bal2 = 0; for(int i = 0; i < n; ++i){ cin >> l[i] >> a[i] >> b[i]; h[i] = {a[i],l[i]}; bal1 += a[i]*l[i]; tar[i] = {b[i],l[i]}; bal2 += b[i]*l[i]; al += l[i]; } if(bal1 != bal2){ cout <<"NIE\n"; continue; } sort(tar.begin(), tar.end()); sort(h.begin(), h.end()); { vector > h2 = h, tar2 = tar; int p1 = 0, p2 = 0, ll = 0; int m1 = 0, m2 = 0; while(ll < al){ int w = min(h2[p1].second,tar2[p2].second); ll += w; m1 += w*h2[p1].first; m2 += w*tar2[p2].first; if(m2 < m1)ok = 0; h2[p1].second -= w; tar2[p2].second -= w; if(h2[p1].second == 0)++p1; if(tar2[p2].second == 0)++p2; } } { vector > h2 = h, tar2 = tar; reverse(h2.begin(),h2.end()); reverse(tar2.begin(),tar2.end()); int p1 = 0, p2 = 0, ll = 0; int m1 = 0, m2 = 0; while(ll < al){ int w = min(h2[p1].second, tar2[p2].second); ll += w; m1 += w*h2[p1].first; m2 += w*tar2[p2].first; if(m2 > m1)ok = 0; h2[p1].second -= w; tar2[p2].second -= w; if(h2[p1].second == 0)++p1; if(tar2[p2].second == 0)++p2; } } if(ok)cout <<"TAK\n"; else cout <<"NIE\n"; } }