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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

long long int t, n;

struct mug {
    long long int vol;
    long long int temp;
};

bool higherTemperature(const mug &a, const mug &b){
     return a.temp > b.temp; 
}

vector<mug> start_mugs;
vector<mug> end_mugs;

int main(){
    scanf("%lld", &t);
    for (int i = 0; i < t; ++i) {
        scanf("%lld", &n);
        for (int j = 0; j < n; ++j) {
            long long int l,a,b;
            scanf("%lld %lld %lld", &l, &a, &b);
            mug startm, endm;
            startm.vol = l;
            startm.temp = a;
            endm.vol = l;
            endm.temp = b;
            
            start_mugs.push_back(startm);
            end_mugs.push_back(endm);
        }
        sort(start_mugs.begin(), start_mugs.end(), higherTemperature);
        sort(end_mugs.begin(), end_mugs.end(), higherTemperature);
        /*
        for (int j = 0; j < n; ++j){
            printf("VOL: %d\nTEMP: %d\n", start_mugs[j].vol, start_mugs[j].temp);
        }
        printf("FINISH:\n");
        for (int j = 0; j < n; ++j){
            printf("VOL: %d\nTEMP: %d\n", end_mugs[j].vol, end_mugs[j].temp);
        }
        */
        int start_idx = 0;
        long long int overQ = 0;
        bool possible = true;
        start_mugs.clear();
        end_mugs.clear();
        
        for(int j = 0; j < n; ++j) {
            // trying to create the endm[i] mug
            long long int neededLiters = end_mugs[j].vol;
            long long int neededEnergy = neededLiters * end_mugs[j].temp;
            long long int availableEnergy = 0;
            
            while(neededLiters > 0){
                if(start_mugs[start_idx].vol > neededLiters){
                    availableEnergy += start_mugs[start_idx].temp * neededLiters;
                    start_mugs[start_idx].vol -= neededLiters;
                    neededLiters = 0;
                } else {
                    availableEnergy += start_mugs[start_idx].temp * start_mugs[start_idx].vol;
                    neededLiters -= start_mugs[start_idx].vol;
                    start_mugs[start_idx].vol = 0;
                    start_idx++;
                }
            }
            
            overQ += availableEnergy - neededEnergy;
            if (overQ < 0){
                possible = false;
            }
        }
        
        if (overQ != 0){
            possible = false;
        }
        
        if(possible){
            printf("TAK\n");
        } else {
            printf("NIE\n");
        }
    }
    return 0;
}