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

typedef std::pair <long long, long long> P;
P A[100005];
P B[100005];

void TC(int jj)
{
	long long SA = 0, SB = 0;
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		int l, a, b;
		scanf("%d %d %d", &l, &a, &b);
		SA += a*l;
		SB += b*l;
		A[i].first = B[i].first = l;
		A[i].second = a;
		B[i].second = b;
	}

	if (SA != SB) {
		printf("NIE\n");
		return;
	}

	auto sorter = [] (P x, P y) { return x.second < y.second; };
	std::sort(B, B+N, sorter);
	std::sort(A, A+N, sorter);

	int ai = 0, bi = 0;
	long long debt = 0;
	while (bi < N) {
		if (B[bi].second > A[ai].second) {
			int diff = B[bi].second - A[ai].second;
			debt += A[ai].first * diff;
			A[ai].second = B[bi].second;
		}

		if (B[bi].second < A[ai].second) {
			int tempdiff = A[ai].second - B[bi].second;
			bool full = (A[ai].first >= B[bi].first);
			int voldiff = full ? B[bi].first : A[ai].first;
			long long temp_needed = tempdiff * voldiff;
			if (temp_needed > debt) {
				printf("NIE\n");
				return;
			}
			debt -= temp_needed;
		}

		if (A[ai].first == B[bi].first) {
			++ai;
			++bi;
		} else if (A[ai].first > B[bi].first) {
			A[ai].first -= B[bi].first;
			++bi;
		} else {
			B[bi].first -= A[ai].first;
			++ai;
		}
	}

	printf("TAK\n");
	return;
}

int main()
{
	int N;
	scanf("%d", &N);

	for (int j = 0; j < N; ++j)
		TC(j);

	return 0;
}