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

using namespace std;

typedef long long int lint;
typedef long double ldouble;
typedef map<int, ldouble> TempToLiters;

struct Problem {
    int maxMam = 0;
    TempToLiters c;
    TempToLiters m;
    string result = "";

    void solve() {
        readData();
        while (result == "") {
            step();
        }
        cout << result << endl;
    }

    void readData() {
        int n; cin >> n;
        lint sa = 0, sb = 0;
        int maxChce = 0;
        for (int i = 0; i < n; ++i) {
            lint l;
            int a, b;
            cin >> l >> a >> b;
            sa += l*a;
            sb += l*b;
            maxMam = max(maxMam, a);
            maxChce = max(maxChce, b);
            addLiters(m, a, l);
            addLiters(c, b, l);
        }

        if (sa != sb) {
            result = "NIE";
        }
        if (maxChce > maxMam) {
            result = "NIE";
        }
    }

    void step() {
        if (c.empty() || m.empty()) {
            if (!m.empty() || !c.empty()) {
                //result = "Gruba kaszana";
                result = "TAK";
            } else {
                result = "TAK";
            }
            return ;
        }

        auto it_c = c.begin();
        auto it_m = m.begin();
        int b = it_c->first;
        ldouble n = it_c->second;
        int a = it_m->first;
        ldouble k = it_m->second;

        if (b < a) { // najmniejszy jaki chce jest mniejszy niz najmniejszy jaki mam
            result = "NIE";
            return;
        }

        if (a == b) {
            //result = "dziwne...";
            result = "TAK";
            return ;
        }

        auto it_ap = m.upper_bound(b);
        if (it_ap == m.end()) {
            result = "NIE";
            return ;
        }
        int ap = it_ap->first;

        ldouble x = n * (ap - b) / (ap - a);
        if (k >= x) {
            removeLiters(m, a, x);
            removeLiters(c, b, n);
            addLiters(c, ap, n-x);
        } else {
            ldouble y = k * (b - a) / (ap - b);
            removeLiters(m, a, k);
            removeLiters(c, b, y+k);
            addLiters(c, ap, y);
        }
    }

    void addLiters(TempToLiters& tempToLiters, int t, ldouble l) {
        tempToLiters[t] += l;
        if (mapContains(c, t) && mapContains(m, t)) {
            ldouble vol = min(c[t], m[t]);
            removeLiters(c, t, vol);
            removeLiters(m, t, vol);
        }
    }

    void removeLiters(TempToLiters& tempToLiters, int t, ldouble l) {
        tempToLiters[t] -= l;
        if (abs(tempToLiters[t]) < 1.0e-9L) {
            tempToLiters.erase(t);
        }
    }

    bool mapContains(const TempToLiters& tempToLiters, int t) {
        return tempToLiters.find(t) != tempToLiters.end();
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    int t; cin >> t;
    while(t--) {
        Problem p;
        p.solve();
    }
    return 0;
}