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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct less_than_key
{
    inline bool operator() (const pair<int, int>& struct1, const pair<int, int> & struct2)
    {
        if(struct1.second == struct2.second){
            return struct1.first < struct2.first;
        }
        return (struct1.second < struct2.second);
    }
};

int main(){
    

    int t;

    cin >> t;


    for(int i = 0; i< t; i ++){

        int k;
        cin >> k;


        vector<pair<int,int>> herbs_expected;
        vector<pair<int,int>> herbs_delivered;
        for(int j = 0; j < k; j ++)
        {
            pair<int, int> tmp;
            cin >> tmp.first;
            cin >> tmp.second;
            herbs_delivered.push_back(tmp);

            cin >> tmp.second;
            herbs_expected.push_back(tmp);
        }
        std::sort(herbs_delivered.begin(), herbs_delivered.end(), less_than_key());
        std::sort(herbs_expected.begin(), herbs_expected.end(), less_than_key());
        
        int64_t leftmass = 0;
        int64_t leftheat = 0;
        int64_t lastmass = 0;
        int64_t lastheat = 0;
        int64_t soupmass = 0;
        int64_t soupheat = 0;
        bool possible = true;
        int left = 0;
        if(herbs_expected[0].second < herbs_delivered[0].second){
            possible = false;
        }
        if(herbs_expected[herbs_expected.size() - 1].second > herbs_delivered[herbs_delivered.size() - 1].second){
            possible = false;
        }
        for(int i = 0; i < herbs_expected.size() && possible; i++){
            
            soupheat += herbs_expected[i].first * herbs_expected[i].second;
            soupmass += herbs_expected[i].first;

            while(left < herbs_expected.size() && (leftheat * soupmass) <= (soupheat * leftmass)) {
                lastmass = leftmass;
                lastheat = leftheat;
                leftmass += herbs_delivered[left].first;
                leftheat += herbs_delivered[left].first * herbs_delivered[left].second;
                left ++;
            }
            if(lastmass < soupmass && (lastheat * soupmass) < (soupheat * lastmass)){
                int64_t leftt = soupmass - lastmass;
                if((lastheat + leftt * herbs_delivered[left - 1].second) > soupheat){
                    possible = false;
                    break;
                }
            }

            if(leftmass < soupmass || (leftheat * soupmass) < (soupheat * leftmass)){
                possible = false;
                break;
            }
        }
        if ((soupmass * leftheat) != (soupheat * leftmass) || leftmass != soupmass || left != herbs_expected.size()) {
            possible = false;
        }
        if(possible){
            cout << "TAK" << endl;
        } else {
            cout << "NIE" << endl;
        }
    }
}