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
#include <bits/stdc++.h>

using namespace std;

#define EPS 0.00000001

int main(){

    int t;
    cin >> t;
    while(t--){
        map<int,int>A;
        int n,a,b,l;
        double sumL=0,sumR=0,tL=0,tR=0;
        cin >> n;
        while(n--){
            cin >> l >> a >> b;
            A[a]+=l;
            A[b]-=l;
        }
        for(auto v=A.begin(); v!=A.end(); v++){
            if(v->second>0){                        //ilosc bitrow
                sumR+=(v->second);
                tR+=(v->first*v->second);
            }
        }
        tR/=sumR;
        //cout << sumR << ' ' <<tR<<endl;
        if(sumR==0){
            cout << "TAK\n";
            continue;
        }
        bool dasie=true;
        for(auto v=A.begin(); v!=A.end(); v++){
            if(v->second>0){
                tL*=sumL;
                tL+=(v->first*v->second);
                sumL+=(v->second);
                tL/=sumL;
                tR*=sumR;
                tR-=(v->first*v->second);
                sumR-=(v->second);
                tR/=sumR;
            }else if(v->second<0){
                //cout << "mamy " << sumL << " herbaty o temp "<< tL << " i " << sumR << " herbaty o temp "<< tR <<endl;
                //cout << "neutralisujemy "<< -v->second << " bitrow hierbaty o temp "<< v->first << endl;
                double sr=(v->second)/-2.0;
                double p=0,k=-(v->second);
                while(k-p>EPS){
                    sr=(p+k)/2.0;
                    if((((tL*sr-(tR*(v->second+sr)))/(-v->second))-(v->first))>0){
                        p=sr;
                    }else{
                        k=sr;
                    }
                }
                //cout <<"trzeba uzyc "<< sr<<" bitrow tea o temp "<< tL<<endl;
                sumL-=sr;
                sumR-=(v->second-sr);
                if(sumL < -EPS || sumR < -EPS){
                    cout << "NIE\n";
                    dasie=false;
                    break;
                }
            }
        }
        if(dasie){
            cout << "TAK\n";
        }
    }
    return 0;
}