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

using namespace std;
double eps = 0.0001;
struct Problem {
    void run() {
        int n;
        cin >> n;
        vector<pair<double, double> > a;
        vector<pair<double, double> > b;
        for (int i = 0; i < n; i++) {
            double l, x, y;
            cin >> l >> x >> y;
            a.emplace_back(x, l);
            b.emplace_back(y, l);
        }

        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        queue<pair<double, double> > wanted;
        for (auto &i:b) {
            wanted.push(i);
        }

        queue<pair<double, double> > cups;
        for (auto &i:a) {
            cups.push(i);
        }

        double temp = 0;
        double litres = 0;

        while (!cups.empty()) {
            pair<double, double> &current_wanted = wanted.front(); //temp, litres

            if (temp > current_wanted.first) {
                break;
            }


            if (litres < current_wanted.second && litres + cups.front().second <= current_wanted.second) {//if not enough litres then add
                temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second);
                litres += cups.front().second;
                cups.pop();
            } else if (temp < current_wanted.first) {//if not enough temperature then add or select
                if ((temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second) <= current_wanted.first) {
                    //if still not enough temperature
                    temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second);
                    litres += cups.front().second;
                    cups.pop();
                } else {
                    double add = (litres * temp - litres * current_wanted.first) / (current_wanted.first - cups.front().first);
                    if(add + litres + eps < current_wanted.second){
                        break;
                    }
                    litres += add;
                    cups.front().second -= add;
                    temp = current_wanted.first;
                }
            }

            if(abs(temp - current_wanted.first) < eps && current_wanted.second <= litres + eps){
                litres -= current_wanted.second;
                wanted.pop();
            }
        }

        if (!wanted.empty()) {
            cout << "NIE" << endl;
        } else {
            cout << "TAK" << endl;
        }
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Problem().run();
    }
}