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 | #include <iostream>
#include <algorithm>
using namespace std;
pair<int,int> A[100000];
pair<int,int> B[100000];
int main() {
int t,n,a,b,c;
cin>>t;
while(t--){
cin>>n;
for(int i =0;i<n;i++){
cin>>a>>b>>c;
A[i].first = b;
A[i].second = a;
B[i].first = c;
B[i].second = a;
};
sort(A,A+n);
sort(B,B+n);
//redukuj
long long AS = 0,BS = 0;
long long AL = 0,BL = 0;
bool ok = true;
AS = 0;
BS = 0;
for(int i =0;i<n;i++){
AS += A[i].first*A[i].second;
BS += B[i].first*B[i].second;
}
if(AS!=BS){
ok = false;
}
AS = 0;
BS = 0;
int i = n-1;
int j = n-1;
while(true){
if(A[i].first > B[j].first){
AS += A[i].first*A[i].second;
AL += A[i].second;
i--;
}
else if(A[i].first == B[j].first){
// cout<<"R";
AS += A[i].first*A[i].second;
AL += A[i].second;
BS += B[j].first*B[j].second;
BL += B[j].second;
i--;
j--;
}
else if(A[i].first < B[j].first){
BS += B[j].first*B[j].second;
BL += B[j].second;
j--;
}
// cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
if(AS<BS){
while(i>=0){
if(AL < BL){
if(AL+A[i].second <= BL){
AS += A[i].first*A[i].second;
AL += A[i].second;
i--;
}else{
long long h = BL-AL;
AS += A[i].first*(h);
AL += h;
A[i].second -=h;
break;
}
}else{
break;
}
// cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
}
//cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
if(AS<BS){
ok = false;
}
}
// cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
if(i<0 || j<0)break;
}
if(ok){
cout<<"TAK\n";
}else{
cout<<"NIE\n";
}
}
return 0;
}
|