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
 98
 99
100
#include <iostream>
#include <algorithm>
using namespace std;
string doit()
{
    int t,ep=0,ek=0;cin>>t;
    pair<int, double> kon[t];
    pair<int, double> pocz[t];
    for(int i=0;i<t;i++){
        cin>>pocz[i].second>>pocz[i].first>>kon[i].first;
        kon[i].second=pocz[i].second;
    }
    sort(kon,kon+t);
    sort(pocz,pocz+t);
    for(int i=0;i<t;i++){
        ep+=pocz[i].first*int(pocz[i].second);
        ek+=kon[i].first*int(kon[i].second);
    }
    if(ep!=ek){return "NIE\n";}
    int pw=t-1,pm=t-1,kt=t-1;
    while(kon[0].second>0.0&&kt>-1&&kon[kt].first<=pocz[pw].first){
        while(pm>-1&&pocz[pm].first>kon[kt].first){pm--;}
        if(pm<0){break;}
        if(kon[kt].first==pocz[pw].first){
            double ppp=min(kon[kt].second,pocz[pw].second);
            kon[kt].second-=ppp;
            pocz[pw].second-=ppp;
            if(kon[kt].second<0.0000001){kon[kt].second=0.0;kt--;}
            if(pocz[pw].second<0.0000001){pocz[pw].second=0.0;pw--;}
        }
        else if(kon[kt].first==pocz[pm].first){
            double ppp=min(kon[kt].second,pocz[pm].second);
            kon[kt].second-=ppp;
            pocz[pm].second-=ppp;
            if(kon[kt].second<0.0000001){kon[kt].second=0.0;kt--;}
            if(pocz[pm].second<0.0000001){pocz[pm].second=0.0;pm--;}
        }
        else{
            double st1=double(kon[kt].first-pocz[pm].first)/double(pocz[pw].first-pocz[pm].first);
            double st2=1.0-st1;
            double warpm=pocz[pm].second-(kon[kt].second*st2),warpw=pocz[pw].second-(kon[kt].second*st1);
            if(warpm<0.0&&warpw<0.0){
                if( ((pocz[pm].second*st1)/st2) > pocz[pw].second){
                    kon[kt].second-=pocz[pw].second/st1;
                    pocz[pm].second-=(pocz[pw].second*st2)/st1;
                    pocz[pw].second=0.0;
                    pw--;
                    if(pocz[pm].second<0.0000001){pm--;}
                    if(kon[kt].second<0.0000001){kt--;}
                }
                else{
                    kon[kt].second-=pocz[pm].second/st2;
                    pocz[pw].second-=(pocz[pm].second*st1)/st2;
                    pocz[pm].second=0.0;
                    pm--;
                    if(pocz[pw].second<0.0000001){pw--;}
                    if(kon[kt].second<0.0000001){kt--;}
                }
            }
            else if(warpm<0.0){
                kon[kt].second-=pocz[pm].second/st2;
                pocz[pw].second-=(pocz[pm].second*st1)/st2;
                pocz[pm].second=0.0;
                pm--;
                if(pocz[pw].second<0.0000001){pw--;}
                if(kon[kt].second<0.0000001){kt--;}
            }
            else if(warpw<0.0){
                kon[kt].second-=pocz[pw].second/st1;
                pocz[pm].second-=(pocz[pw].second*st2)/st1;
                pocz[pw].second=0.0;
                pw--;
                if(pocz[pm].second<0.0000001){pm--;}
                if(kon[kt].second<0.0000001){kt--;}
            }
            else{kon[kt].second=0.0; kt--; pocz[pm].second=warpm; pocz[pw].second=warpw;
                if(warpm<0.0000001){pocz[pm].second=0.0;pm--;}
                if(warpw<0.0000001){pocz[pw].second=0.0;pw--;}
            }
        }
    }
    if(kt<0||kon[0].second<0.0001){return "TAK\n";}
    else{return "NIE\n";}
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n;cin>>n;
    for(int i=0;i<n;i++){ cout<<doit(); }
        //cout<<"posortowane:";
    //for(int i=0;i<t;i++){cout<<pocz[i].first<<" :: "<<pocz[i].second<<' ';}
    //cout<<'\n';
    //for(int i=0;i<t;i++){cout<<kon[i].first<<" :: "<<kon[i].second<<' ';}
    //cout<<'\n';
    //cout<<ep<<' '<<ek<<'\n';
    //cout<<"Wm: "<<pocz[pw].second<<"Wt: "<<pocz[pw].first<<"Mm: "<<pocz[pm].second<<"Mt: "<<pocz[pm].first<<"Km: "<<kon[kt].second<<"Kt: "<<kon[kt].first<<'\n';
    /*cout<<":"<<kt<<' '<<kon[0].second<<'\n';*/
    return 0;
}