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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;

bool sortingComparator(pair<double, double> a, pair<double, double> b)
{
	return a.second > b.second;
}

pair<double, double> mix(pair<double, double> a, pair<double, double> b)
{
	double v = a.first + b.first;
	double t = (a.first * a.second + b.first * b.second) / (a.first + b.first);
	return make_pair(v, t);
}

pair<double, double> get_proporcions(pair<double, double> a, pair<double, double> b, double t, double v)
{
	double va = v * (t - b.second) / (a.second - b.second);
	double vb = v - va;
	return make_pair(va, vb);
}

int t, n;
double l, a, b;

int main()
{
	ios_base::sync_with_stdio(false);

	//pair<double, double> test = get_proporcions(make_pair(2, 6), make_pair(3, 2), 5, 3);
	//cout << test.first << " " << test.second;
	//system("PAUSE");
	cin >> t;
	while (t > 0)
	{
		cin >> n;

		vector<pair<double, double>> required;
		vector<pair<double, double>> owned;

		for (int i = 0; i < n; i++)
		{
			cin >> l >> a >> b;
			required.push_back(make_pair(l, b));
			owned.push_back(make_pair(l, a));
		}

		sort(required.begin(), required.end(), sortingComparator);
		sort(owned.begin(), owned.end(), sortingComparator);

		while (required.size() != 0 && owned.size() != 0 && required.front().second <= owned.front().second)
		{
			pair<double, double> req = required.front();
			while (owned.size() > 0 && owned[0].second == required[0].second && owned[0].first == required[0].first)
			{
				owned.erase(owned.begin());
				required.erase(required.begin());
			}
			if (owned.size() == 0 || required.size() == 0)
				break;
			while (owned.size() > 1 && owned[1].second != required[0].second)
			{
				pair<double, double> mixed = mix(owned[0], owned[1]);

				if (mixed.second <= req.second)
					break;

				owned.erase(owned.begin());
				owned.erase(owned.begin());
				owned.insert(owned.begin(), mixed);
			}

			if (owned[1].second == required[0].second)
			{
				if (owned[1].first == required[0].first)
				{
					owned.erase(owned.begin());
				}
				else if (owned[1].first > required[0].first)
				{
					owned[1].first -= required[0].first;
					required.erase(required.begin());
				}
				else
				{
					required[0].first -= owned[1].first;
					owned.erase(owned.begin() + 1);
				}
				continue;
			}

			if (owned.size() == 1)
			{
				if (owned[0].first == required[0].first && owned[0].second == required[0].second)
				{
					owned.erase(owned.begin());
					required.erase(required.begin());
				}
			}
			else
			{
				if (owned[0].second == required[0].second)
				{
					if (required[0].first > owned[0].first)
						break;
					owned[0].first -= required[0].first;
					required.erase(required.begin());
					if (owned[0].first == 0)
						owned.erase(owned.begin());
				}
				else
				{
					pair<double, double> quantity = get_proporcions(owned[0], owned[1], req.second, req.first);
					owned[0].first -= quantity.first;
					owned[1].first -= quantity.second;
					if (owned[1].first == 0)
						owned.erase(owned.begin() + 1);
					if (owned[0].first == 0)
						owned.erase(owned.begin());
					required.erase(required.begin());
				}
			}
			if (owned.size() == 1 && required.size() == 1)
			{
				if (owned[0].second == required[0].second && owned[0].first == required[0].first)
				{
					owned.erase(owned.begin());
					required.erase(required.begin());
				}
				break;
			}
		}

		if (required.size() == 0 && owned.size() == 0)
			cout << "TAK\n";
		else
			cout << "NIE\n";

		t--;
	}
}