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
#include <stack>
#include <utility>
#include <cstdio>
#include <map>
using namespace std; 

const long double EPS = 10e-9;

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

	while(t--) {
		bool success = true;

		int n;
		scanf("%d", &n);

		stack<pair<int, long double> > caps;
		map<int, long double> tea_in_temp;

		long long sum_a = 0, sum_b = 0;
		for(int i=0; i<n; ++i) {
			int l, a, b;
			scanf("%d %d %d", &l, &a, &b);

			sum_a += (l * a);
			sum_b += (l * b);

			caps.push(make_pair(b, l));
			tea_in_temp[a] += l;
		}

		if(sum_a != sum_b) {
			success = false;			
		}

		while(!caps.empty() && success) {
			int cap_temp = caps.top().first;
			long double cap_vol = caps.top().second;
			caps.pop();

			map<int, long double>::iterator it = tea_in_temp.find(cap_temp);

			if(it != tea_in_temp.end() && it->second > EPS) {

				if(it->second - cap_vol > EPS) {
					it->second -= cap_vol;
				} else if(it->second - cap_vol < EPS && it->second - cap_vol > -EPS) {
					tea_in_temp.erase(it);
				} else {
					caps.push(make_pair(cap_temp, cap_vol - it->second));
					tea_in_temp.erase(it);
				}
			} else {
				map<int, long double>::iterator it_low = tea_in_temp.lower_bound(cap_temp);
				map<int, long double>::iterator it_upp = tea_in_temp.lower_bound(cap_temp);
				if(it_low == tea_in_temp.begin()) {
					success = false;
					break;
				}
				if(it_upp == tea_in_temp.end()) {
					success = false;
					break;
				}

				it_low--;

				int ta = it_low->first;
				int tb = it_upp->first;
				int tc = cap_temp;
				long double c = cap_vol;

				long double a = c * ((long double) (tc - tb))/((long double) (ta - tb));
				long double b = c - a;

				caps.push(make_pair(ta, a));
				caps.push(make_pair(tb, b));
			}
		}

		if(success) printf("TAK\n");
		else printf("NIE\n");
	}
}