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

typedef std::tuple<int, int, int> dataType;

bool check_data() {
	int n;
	scanf("%d", &n);
	std::vector<dataType> data;
	for (int i = 0; i < n; i++) {
		int size, start_temp, end_temp;
		scanf("%d %d %d", &size, &start_temp, &end_temp);
		auto t = dataType(size, start_temp, end_temp);
		data.push_back(t);
	}
	std::vector<dataType> new_data(data);
	std::sort(begin(data), end(data), [](auto const &t1, auto const &t2) {
		return std::get<1>(t1) > std::get<1>(t2); // or use a custom compare function
	}); 
	std::sort(begin(new_data), end(new_data), [](auto const &t1, auto const &t2) {
		return std::get<2>(t1) < std::get<2>(t2); // or use a custom compare function
	});
	long long int size_sum = 0;
	long long int energy_sum = 0;
	long long int new_mas = 0;
	long long int new_energy = 0;
	double new_avg_temp;
	double avg_temp;
	for (auto it = data.begin() ; it != data.end(); ++it) {
		auto set = *it;
		size_sum += std::get<0>(set);
		energy_sum += std::get<0>(set) * std::get<1>(set);
		avg_temp = (double) energy_sum / (double) size_sum;
		dataType last = new_data.back();
		while(!new_data.empty() && (size_sum >= new_mas + std::get<0>(last))) {
			new_data.pop_back();
			new_energy += std::get<0>(last) * std::get<2>(last);
			new_mas += std::get<0>(last); 
			if (!new_data.empty())
				last = new_data.back();
		}
		if (!new_data.empty()) {
			int missing_mas = size_sum - new_mas;
			new_energy += missing_mas * std::get<2>(last);
			new_mas += missing_mas;
			new_data.pop_back();
			new_data.push_back(dataType(std::get<0>(last) - missing_mas, std::get<1>(last), std::get<2>(last)));
		}
		new_avg_temp = (double) new_energy / (double) new_mas;
		if (avg_temp < new_avg_temp) {
			return false;
		}
	}
	avg_temp =  (double) energy_sum / (double) size_sum;
	if (avg_temp != new_avg_temp) {
		return false;
	}
	// sprawdz warunki w druga strone::

	std::vector<dataType> new_data1(data);
	new_data = new_data1;
	// posortuj data po temp poczatkowej malejaco MAX -> MIN
	std::sort(begin(data), end(data), [](auto const &t1, auto const &t2) {
		return std::get<2>(t1) < std::get<2>(t2); // or use a custom compare function
	}); 
	std::sort(begin(new_data), end(new_data), [](auto const &t1, auto const &t2) {
		return std::get<1>(t1) > std::get<1>(t2); // or use a custom compare function
	});
	size_sum = 0;
	energy_sum = 0;
	new_mas = 0;
	new_energy = 0;
	for (auto it = data.begin() ; it != data.end(); ++it) {
		auto set = *it;
		size_sum += std::get<0>(set);
		energy_sum += std::get<0>(set) * std::get<2>(set);
		avg_temp = (double) energy_sum / (double) size_sum;
		dataType last = new_data.back();
		while(!new_data.empty() && (size_sum >= new_mas + std::get<0>(last))) {
			new_data.pop_back();
			new_energy += std::get<0>(last) * std::get<1>(last);
			new_mas += std::get<0>(last); 
			if (!new_data.empty())
				last = new_data.back();
		}
		if (!new_data.empty()) {
			long long missing_mas = size_sum - new_mas;
			new_energy += missing_mas * std::get<1>(last);
			new_mas += missing_mas;
			new_data.pop_back();
			new_data.push_back(dataType(std::get<0>(last) - missing_mas, std::get<1>(last), std::get<2>(last)));
		}
		new_avg_temp = (double) new_energy / (double) new_mas;
		if (avg_temp < new_avg_temp) {
			return false;
		}
	}
	avg_temp =  (double) energy_sum / (double) size_sum;
	if (avg_temp == new_avg_temp) {
		return true;
	}
	return false;
}

int main() {
	int t;
	scanf("%d", &t);
	for (int set = 0; set < t; set++) {
		bool ans = check_data();
		if (ans)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
}