#include <bits/stdc++.h> using namespace std; double eps = 0.0001; struct Problem { void run() { int n; cin >> n; vector<pair<double, double> > a; vector<pair<double, double> > b; for (int i = 0; i < n; i++) { double l, x, y; cin >> l >> x >> y; a.emplace_back(x, l); b.emplace_back(y, l); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); queue<pair<double, double> > wanted; for (auto &i:b) { wanted.push(i); } queue<pair<double, double> > cups; for (auto &i:a) { cups.push(i); } double temp = 0; double litres = 0; while (!cups.empty()) { pair<double, double> ¤t_wanted = wanted.front(); //temp, litres if (temp > current_wanted.first) { break; } if (litres < current_wanted.second && litres + cups.front().second <= current_wanted.second) {//if not enough litres then add temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second); litres += cups.front().second; cups.pop(); } else if (temp < current_wanted.first) {//if not enough temperature then add or select if ((temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second) <= current_wanted.first) { //if still not enough temperature temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second); litres += cups.front().second; cups.pop(); } else { double add = (litres * temp - litres * current_wanted.first) / (current_wanted.first - cups.front().first); if(add + litres + eps < current_wanted.second){ break; } litres += add; cups.front().second -= add; temp = current_wanted.first; } } if(abs(temp - current_wanted.first) < eps && current_wanted.second <= litres + eps){ litres -= current_wanted.second; wanted.pop(); } } if (!wanted.empty()) { cout << "NIE" << endl; } else { cout << "TAK" << endl; } } }; int main() { int t; cin >> t; while (t--) { Problem().run(); } }
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 | #include <bits/stdc++.h> using namespace std; double eps = 0.0001; struct Problem { void run() { int n; cin >> n; vector<pair<double, double> > a; vector<pair<double, double> > b; for (int i = 0; i < n; i++) { double l, x, y; cin >> l >> x >> y; a.emplace_back(x, l); b.emplace_back(y, l); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); queue<pair<double, double> > wanted; for (auto &i:b) { wanted.push(i); } queue<pair<double, double> > cups; for (auto &i:a) { cups.push(i); } double temp = 0; double litres = 0; while (!cups.empty()) { pair<double, double> ¤t_wanted = wanted.front(); //temp, litres if (temp > current_wanted.first) { break; } if (litres < current_wanted.second && litres + cups.front().second <= current_wanted.second) {//if not enough litres then add temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second); litres += cups.front().second; cups.pop(); } else if (temp < current_wanted.first) {//if not enough temperature then add or select if ((temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second) <= current_wanted.first) { //if still not enough temperature temp = (temp*litres + cups.front().first * cups.front().second) / (litres + cups.front().second); litres += cups.front().second; cups.pop(); } else { double add = (litres * temp - litres * current_wanted.first) / (current_wanted.first - cups.front().first); if(add + litres + eps < current_wanted.second){ break; } litres += add; cups.front().second -= add; temp = current_wanted.first; } } if(abs(temp - current_wanted.first) < eps && current_wanted.second <= litres + eps){ litres -= current_wanted.second; wanted.pop(); } } if (!wanted.empty()) { cout << "NIE" << endl; } else { cout << "TAK" << endl; } } }; int main() { int t; cin >> t; while (t--) { Problem().run(); } } |