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

struct cup {
    int l;
    int t;
    bool operator<(const struct cup& par) {
        return (t < par.t);
    }
};

void show(struct cup* t, int n) {
    int i;
    std::cerr << "{";
    for (i = 0; i < n; ++i) {
        std::cerr << i << "(" << t[i].t << "; " << t[i].l << "), ";
    }
    std::cerr << "}\n";
}

#define MIN(A, B) (((A) < (B)) ? (A) : (B))

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t, ti, n, l, a, b, ni, ui, uw, i, j;
    int64_t suma, sumb, energy, dt;
    cup is[100000], want[100000];
    bool fail;

    std::cin >> t;
    for (ti = 0; ti < t; ++ti) {
        ui = uw = 0;
        suma = sumb = 0;
        std::cin >> n;
        for (ni = 0; ni < n; ++ni) {
            std::cin >> l >> a >> b;
            is[ui].l = l;
            is[ui].t = a;
            ui++;
            want[uw].l = l;
            want[uw].t = b;
            uw++;
            suma += l * a;
            sumb += l * b;
        }
        if (suma != sumb) {
            fail = true;
        } else {
            std::sort(is, is + ui);
            std::sort(want, want + uw);
            energy = 0;
            i = 0;
            j = 0;
            fail = false;
            while ((i < ui) && (j < uw)) {
                l = MIN(is[i].l, want[j].l);
                is[i].l -= l;
                want[j].l -= l;
                dt = is[i].t - want[j].t;
                energy -= dt * l;
                if (energy < 0) {
                    fail = true;
                    break;
                }
                if (is[i].l == 0) i++;
                if (want[j].l == 0) j++;
            }
            if ((i != ui) || (j != uw) || (energy != 0)) {
                fail = true;
            }
        }
        if (fail) {
            std::cout << "NIE\n";
        } else {
            std::cout << "TAK\n";
        }
    }
    return 0;
}