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 <iostream>
#include <unordered_map>
#include <set>
#include <utility>
#define EPSILON ((long double)1 / (long double)1000000000000)
using namespace std;

long long t, n;
set<long long> availableKeys;
unordered_map<long long, long double> availableTemps;
pair<long long, long double> targets[100005];

long long li, ai, bi;

long double absLD(long double x){
	return (x < 0 ? -x : x);	
}

bool solve(long long x){
	long double left = (long double)targets[x].first;
	long long requiredTemp = targets[x].second;
	
	//try equal
	auto it = availableKeys.lower_bound(requiredTemp);
	if(*it == requiredTemp){
		//we found exactly the temperature we need
		long double maxToRemove = min(left, availableTemps[*it]);
		availableTemps[*it] -= maxToRemove;
		left -= maxToRemove;
		if(availableTemps[*it] == 0) availableKeys.erase(it);
	}
	if(left == 0) return true;
	
	//try balance <-1 1->
	it = availableKeys.lower_bound(requiredTemp);
	while(it != availableKeys.end() && absLD(left) > EPSILON){
		if(it == availableKeys.begin()) return false; //cannot balance - no lower temp.
		auto it2 = it;
		it--;
		
		//it <-d-> value <-d2-> it2
		long double tempA = *it;
		long double tempB = *it2;
		long double ratio = 1 / ((long double)(requiredTemp - tempA) / (long double)(tempB - requiredTemp)); //ratio of it to it2
		long double partA = ratio / (ratio + 1);
		long double partB = 1 - partA;
		long double maxAllowed = left;
		maxAllowed = min(maxAllowed, availableTemps[tempA] * (1 / partA));
		maxAllowed = min(maxAllowed, availableTemps[tempB] * (1 / partB));
		
		left -= maxAllowed;
		availableTemps[tempA] -= maxAllowed * partA;
		if(absLD(availableTemps[tempA]) <= EPSILON) availableKeys.erase(tempA);
		availableTemps[tempB] -= maxAllowed * partB;
		if(absLD(availableTemps[tempB]) <= EPSILON) availableKeys.erase(tempB);
		
		it = availableKeys.lower_bound(requiredTemp);
	}
	if(absLD(left) <= EPSILON) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	for(long long q = 0; q < t; q++){
		availableTemps.clear();
		availableKeys.clear();
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> li >> ai >> bi;
			targets[i] = make_pair(li, (long double)bi);
			availableKeys.insert(ai);
			availableTemps[ai] += (long double)li;
		}
		bool ok = true;
		for(int i = 0; i < n; i++) if(!solve(i)){
			ok = false;
			break;
		}
		cout << (ok ? "TAK\n" : "NIE\n");
	}
}