#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(); } } |
English