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

using ll = long long;




int main()
{
  std::ios::sync_with_stdio(false);

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;

    ll check_pre = 0, check_after = 0;
    std::vector<std::pair<ll, ll>> temps, desired;
    temps.reserve(n);
    desired.reserve(n);

    for (int i = 0; i < n; ++i) {
      long long l, a, b;
      std::cin >> l >> a >> b;
      temps.emplace_back(a, l);
      desired.emplace_back(b, l);
      check_pre += a * l;
      check_after += b * l;
    }

    if (check_pre != check_after) {
      std::cout << "NIE" << std::endl;
      continue;
    }

    std::sort(std::begin(temps), std::end(temps));
    std::sort(std::begin(desired), std::end(desired));

    bool possible = true;
    ll spare = 0;
    while (possible && !temps.empty()) {
      auto&[t, w] = temps.back();
      auto&[d, l] = desired.back();

      if (d <= t) {
        // temp is higher or equal than desired
        if (w < l) {
          // there is less buckets with t temp
          spare += (t - d) * w;
          l -= w;
          temps.pop_back();
        } else if (l < w) {
          // there is less buckets with d temp
          spare += (t - d) * l;
          w -= l;
          desired.pop_back();
        } else {
          // there is exactly the same number of bins
          spare += (t - d) * l;
          temps.pop_back();
          desired.pop_back();
        }
      } else if (spare > 0) {
        // temp is lower than desired and we have some spare heat
        if (w < l) {
          spare -= (d - t) * w;
          l -= w;
          temps.pop_back();
        } else if (l < w) {
          spare -= (d - t) * l;
          w -= l;
          desired.pop_back();
        } else {
          spare -= (d - t) * l;
          temps.pop_back();
          desired.pop_back();
        }
        if (spare < 0) {
          possible = false;
        }
      } else {
        possible = false;
      }
    }

    std::cout << (possible ? "TAK" : "NIE") << std::endl;
  }

  return 0;
}