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 #include using namespace std; typedef long long int lint; typedef long double ldouble; typedef map 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; }