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

int main() {
  int t, n;
  long long int l, a, b;

  scanf("%d", &t);

  for (int i = 0; i < t; i++) {
    std::vector<std::pair<long long int, long long int>> av;
    std::vector<std::pair<long long int, long long int>> bv;
    scanf("%d", &n);

    for (int j = 0; j < n; j++) {
      scanf("%lld %lld %lld", &l, &a, &b);
      av.push_back(std::make_pair(a, l));
      bv.push_back(std::make_pair(b, l));
    }

    std::sort(av.begin(), av.end());
    std::sort(bv.begin(), bv.end());

    long long int la = 0;
    long long int lb = 0;
    long long int ha = 0;
    long long int hb = 0;
    long long int pos = 0;

    int idx_a = 0;
    int idx_b = 0;

    bool was_break = false;

    for (int k = 0; k < 2 * n - 1; k++) {
      if (la + av[idx_a].second <= lb + bv[idx_b].second) {
        la = la + av[idx_a].second;
        ha += (std::max(la, lb) - pos) * av[idx_a].first;
        hb += (std::max(la, lb) - pos) * bv[idx_b].first;
        idx_a += 1;
      } else {
        lb = lb + bv[idx_b].second;
        ha += (std::max(la, lb) - pos) * av[idx_a].first;
        hb += (std::max(la, lb) - pos) * bv[idx_b].first;
        idx_b += 1;
      }

      if (ha > hb) {
        was_break = true;
        break;
      }

      pos = std::max(la, lb);
    }

    if (ha > hb || (ha != hb && !was_break)) {
      printf("NIE\n");
    } else {
      printf("TAK\n");
    }
  }

  return 0;
}