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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <memory>

#define DEBUG(x)

struct MinMax
{
    long long int min;
    long long int max;

    MinMax()
        : min(std::numeric_limits<long long int>::max()),
          max(std::numeric_limits<long long int>::min())
    {}

    inline void add(long long int number) {
        if (number < min)
            min = number;
        if (number > max)
            max = number;
    }
};

struct CupMeta
{
    long long int temperature;
    long long int requested_delta_q;
    long long int volume;
    double t_current;
    long long int t_final;

    CupMeta(long long int t, long long int rdq, long long int v)
        : temperature(t),
          requested_delta_q(rdq),
          volume(v)
    {
        t_current = t;
        t_final = 0.0;
    }
};

bool is_0_law_valid(std::vector<std::shared_ptr<CupMeta>> &cups)
{
    auto cups_current = cups;

    for (auto it = cups.end() - 1; it >= cups.begin(); --it) {
        if ((*it)->requested_delta_q == 0)
            continue;
        
        std::sort(cups_current.begin(), cups_current.end(), [](const auto &lhs, const auto &rhs){
            return lhs->t_current > rhs->t_current;
        });

        // iterate over next cups
        for (auto jt = cups_current.end() - 1; jt >= cups_current.begin(); --jt) {
            // heat up
            if (((*it)->requested_delta_q > 0) && ((*jt)->requested_delta_q < 0) && ((*it)->t_current < (*jt)->t_current)) {
                // energy transfer
                const long long int v = std::min((*it)->volume, (*jt)->volume);
                const long long int max_transfer = ((*jt)->t_current - (*it)->t_current) * v;
                long long int transfer = std::min(std::min((*it)->requested_delta_q, -(*jt)->requested_delta_q), max_transfer);

                (*it)->requested_delta_q -= transfer;
                (*it)->t_current += static_cast<double>(transfer) / (*it)->volume;

                (*jt)->requested_delta_q += transfer;
                (*jt)->t_current -= static_cast<double>(transfer) / (*jt)->volume;

                if ((*it)->requested_delta_q == 0) {
                    break;
                }
            }
        }
    }

    for (const auto &cup : cups) {
        if (cup->requested_delta_q != 0) {
            DEBUG(std::cout << "STOP at = " << cup->temperature << std::endl;)
            return false;
        }
    }

    return true;
}

void solve_set()
{
    DEBUG(std::cout << "\nSTART\n";)

    int n_kids;
    std::cin >> n_kids;

    int energy_current = 0;
    MinMax temp_current_meta;
    MinMax temp_expected_meta;

    std::vector<std::shared_ptr<CupMeta>> cups;
    cups.reserve(n_kids);

    for (int i = 0; i < n_kids; ++i) {
        long long int l;
        long long int a;
        long long int b;
        std::cin >> l >> a >> b;
        
        energy_current += l * (a - b);
        temp_current_meta.add(a);
        temp_expected_meta.add(b);

        cups.push_back(std::make_shared<CupMeta>(a, l * (b - a), l));
        cups.back()->t_final = b;
    }

    if (energy_current != 0
            || temp_expected_meta.min < temp_current_meta.min 
            || temp_expected_meta.max > temp_current_meta.max) {
        std::cout << "NIE\n";
        return;
    }

    std::sort(cups.begin(), cups.end(), [](const auto &lhs, const auto &rhs){
        return lhs->t_final < rhs->t_final;
    });

    DEBUG(for (const auto &cup : cups) { std::cout << "t = " << cup->temperature << " rdq = " << cup->requested_delta_q << " v = " << cup->volume << " t_final = " << cup->t_final << " t_current = " << cup->t_current << std::endl; })
    if (!is_0_law_valid(cups)) {
        std::cout << "NIE\n";
        return;
    }
    DEBUG(for (const auto &cup : cups) { std::cout << "t = " << cup->temperature << " rdq = " << cup->requested_delta_q << " v = " << cup->volume << " t_final = " << cup->t_final << " t_current = " << cup->t_current << std::endl; })

    std::cout << "TAK\n";
}

int main()
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        solve_set();
    }
    return 0;
}