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