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