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
#include <iostream>
int comparison(const void* a, const void* b) {
	std::pair<int, int> *t1 = (std::pair<int, int>*)(a);
	std::pair<int, int> *t2 = (std::pair<int, int>*)(b);
	if (t1->first > t2->first) return -1;
	else if (t1->first == t2->first) return 0;
	else return 1;
}
int main()
{
	int number_of_sets;
	std::cin >> number_of_sets;
	for (int i = 0; i < number_of_sets; ++i)
	{
		int number_of_cups;
		std::pair<int, int> *set1, *set2;
		std::cin >> number_of_cups;
		set1 = new std::pair<int, int>[number_of_cups];
		set2 = new std::pair<int, int>[number_of_cups];
		for (int j = 0; j < number_of_cups; ++j)
		{
			int quantity;
			int temp;
			std::cin >> quantity;
			std::cin >> temp;
			set1[j] = std::make_pair(temp, quantity);
			std::cin >> temp;
			set2[j] = std::make_pair(temp, quantity);
		}
		std::qsort(set1, number_of_cups, sizeof(std::pair<int, int>), comparison);
		std::qsort(set2, number_of_cups, sizeof(std::pair<int, int>), comparison);
		bool good = true;
		int primary_index[4] = { 0, 0 };
		int secondary_index[4] = { 1, 1};
		int diff_sum = 0;
		while (true)
		{
			int x = set1[primary_index[0]].first - set2[primary_index[1]].first;//max diff
			diff_sum += x;
			if (diff_sum < 0)
			{
				good = false;
				break;
			}
			++secondary_index[0];
			if (secondary_index[0] > set1[primary_index[0]].second)
			{
				secondary_index[0] = 1;
				++primary_index[0];
			}
			++secondary_index[1];
			if (secondary_index[1] > set2[primary_index[1]].second)
			{
				secondary_index[1] = 1;
				++primary_index[1];
			}
			if (primary_index[0] > number_of_cups - 1 || primary_index[1] > number_of_cups - 1)
			{
				break;
			}
		}
		if (good && !diff_sum)
		{
			std::cout <<"TAK\n";
		}
		else
		{
			std::cout <<"NIE\n";
		}
		delete set1;
		delete set2;
	}
	return 0;
}