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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define DEBUGCOUT(x) 

class Tea {
public:
	long double volume;
	long double temp;

	Tea(int volume, int temp) {
		this->volume = volume;
		this->temp = temp;
	}
};

const long double MIN_VALUE = std::numeric_limits<long double>::epsilon() * 10e6;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	DEBUGCOUT(MIN_VALUE);

	for (int i = 0; i < t; ++i) {
		int teasCount;
		std::vector<Tea> currentTeas, desiredTeas;

		cin >> teasCount;

		currentTeas.reserve(teasCount);
		desiredTeas.reserve(teasCount);

		for (int teaNumber = 0; teaNumber < teasCount; ++teaNumber) {
			int volume, currentTemp, desiredTemp;
			cin >> volume >> currentTemp >> desiredTemp;

			currentTeas.push_back(Tea(volume, currentTemp));
			desiredTeas.push_back(Tea(volume, desiredTemp));
		}

		sort(currentTeas.begin(), currentTeas.end(), [](Tea& tea1, Tea& tea2) {
			return tea1.temp < tea2.temp;
		});

		sort(desiredTeas.begin(), desiredTeas.end(), [](Tea& tea1, Tea& tea2) {
			return tea1.temp < tea2.temp;
		});

		Tea coldestTea = currentTeas[0];

		unsigned int desiredPos(0), currentPos(1);
		bool canRedistribute = true;

		while (currentPos < currentTeas.size() && desiredPos < desiredTeas.size()) {
			DEBUGCOUT("currentPos = " << currentPos << ", desiredPos = " << desiredPos);

			Tea& desiredTea = desiredTeas[desiredPos];
			Tea& currentTea = currentTeas[currentPos];

			if (desiredTeas[desiredPos].temp < coldestTea.temp) {
				DEBUGCOUT("desired tea is colder than the coldest tea");
				canRedistribute = false;
				break;
			}

			if (desiredTeas[desiredPos].temp >= currentTeas[currentPos].temp) {
				// can't go to desired temp so mixing both teas
				DEBUGCOUT("can't go to the desired temp so mixing both teas");
				coldestTea.temp = (coldestTea.volume*coldestTea.temp + currentTea.volume*currentTea.temp)/(coldestTea.volume + currentTea.volume);
				coldestTea.volume += currentTea.volume;

				++currentPos;
				break;
			}

			double neededCurrentTeaVolume = (desiredTea.temp - coldestTea.temp)*coldestTea.volume / (currentTea.temp - desiredTea.temp);

			if (neededCurrentTeaVolume > currentTea.volume) {
				// can't go to desired temp so mixing both teas
				DEBUGCOUT("can't go to the desired temp so mixing both teas 2");
				coldestTea.temp = (coldestTea.volume*coldestTea.temp + currentTea.volume*currentTea.temp) / (coldestTea.volume + currentTea.volume);
				coldestTea.volume += currentTea.volume;

				++currentPos;
				break;
			}

			DEBUGCOUT("moving coldestTea to " << desiredTea.temp);
			coldestTea.temp = desiredTea.temp;
			coldestTea.volume += neededCurrentTeaVolume - desiredTea.volume;
			currentTea.volume -= neededCurrentTeaVolume;

			++desiredPos;
			if (coldestTea.volume < -MIN_VALUE) canRedistribute = false;

		}

		if (currentPos >= currentTeas.size()) {
			// We used all the teas and now the last desired should have the same temp and volume as coldest one
			DEBUGCOUT("last desired tea left");
			canRedistribute = canRedistribute && abs(coldestTea.volume - desiredTeas[desiredPos].volume) < MIN_VALUE
				&& abs(coldestTea.temp - desiredTeas[desiredPos].temp) < MIN_VALUE && desiredPos == desiredTeas.size() - 1;
		} else if (desiredPos >= desiredTeas.size()) {
			// We mixed all the desired teas and now the coldest tea should have 0 volume
			DEBUGCOUT("last current tea left");
			DEBUGCOUT("Coldest tea volume: " << coldestTea.volume);
			canRedistribute = canRedistribute && abs(coldestTea.volume) < MIN_VALUE;
		}
		
		cout << (canRedistribute ? "TAK" : "NIE") << "\n";

		DEBUGCOUT("==================\n==================\n==================\n==================\n");

	}
}