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

struct Mug {
    int capacity;
    double temperature;
    [[nodiscard]] double energy() const {
        return capacity * temperature;
    }
    bool operator<(const Mug &other) const {
        return temperature < other.temperature;
    }
    void combine(const Mug &other) {
        double totalEnergy = energy() + other.energy();
        capacity += other.capacity;
        temperature = totalEnergy / capacity;
    }
    static auto empty() {
        return Mug{0, 0};
    }
};

struct MugArray {
    int size;
    Mug mugs[100000];
} actual, expected;

struct MugIterator {
    int currentMug;
    MugArray &mugArray;
    explicit MugIterator(MugArray &mugArray) : currentMug(0), mugArray(mugArray) {}
    auto consume(int capacity) {
        double retEnergy = 0;
        while (mugArray.mugs[currentMug].capacity < capacity) {
            retEnergy += mugArray.mugs[currentMug].energy();
            capacity -= mugArray.mugs[currentMug].capacity;
            mugArray.mugs[currentMug].capacity = 0;
            ++currentMug;
        }
        retEnergy += capacity * mugArray.mugs[currentMug].temperature;
        mugArray.mugs[currentMug].capacity -= capacity;
        return retEnergy;
    }
};

void processDataSet();

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        processDataSet();
    }
    return 0;
}

void processDataSet() {
    double expectedEnergy = 0, actualEnergy = 0;
    std::cin >> expected.size;
    actual.size = expected.size;
    for (auto i = 0; i < expected.size; ++i) {
        std::cin >> actual.mugs[i].capacity >> actual.mugs[i].temperature >> expected.mugs[i].temperature;
        expected.mugs[i].capacity = actual.mugs[i].capacity;
        expectedEnergy += expected.mugs[i].energy();
        actualEnergy += actual.mugs[i].energy();
    }
    if (expectedEnergy != actualEnergy) {
        std::cout << "NIE\n";
        return;
    }
    std::sort(actual.mugs, actual.mugs + actual.size);
    std::sort(expected.mugs, expected.mugs + expected.size);

    MugIterator iter(actual);
    Mug compositeActual = Mug::empty();
    Mug compositeExpected = Mug::empty();
    for (int i = 0; i < expected.size; ++i) {
        compositeExpected.combine(expected.mugs[i]);
        double consumedTemperature = iter.consume(expected.mugs[i].capacity) / expected.mugs[i].capacity;
        compositeActual.combine(Mug{expected.mugs[i].capacity, consumedTemperature});
        if (compositeExpected < compositeActual) {
            std::cout << "NIE\n";
            return;
        }
    }
    std::cout << "TAK\n";
}