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
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
//Kisielinski Damian
using namespace std;

struct Person
{
    double litre;
		double currTemp;
		double tarrTemp;
};

vector<int> sortIndexesCurr(Person * v, int len) {
  vector<int> idx(len);
  iota(idx.begin(), idx.end(), 0);

  sort(idx.begin(), idx.end(),
       [v](int i1, int i2) {return v[i1].currTemp > v[i2].currTemp;});

  return idx;
}

vector<int> sortIndexesTarr(Person * v, int len) {
  vector<int> idx(len);
  iota(idx.begin(), idx.end(), 0);

  sort(idx.begin(), idx.end(),
       [v](int i1, int i2) {return v[i1].tarrTemp > v[i2].tarrTemp;});

  return idx;
}

bool areSame(double a, double b)
{
    return (a - b) > 0 ? (a - b) < 0.000000001 : (b-a) < 0.000000001;
}

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(0);
	int n, t;
	cin>>t;
	for (int i = 0; i < t; i++) {
    //cout<<"Zestaw: "<<i<<endl;
		cin>>n;
		Person tab[n];
		double currSum=0, tarrSum=0;
		for (int j = 0; j < n; j++) {
			cin>>tab[j].litre>>tab[j].currTemp>>tab[j].tarrTemp;
			currSum+=(long)tab[j].currTemp;
			tarrSum+=(long)tab[j].tarrTemp;
		}
		if (currSum != tarrSum) {
			cout<<"NIE"<<endl;
			continue;
		}
		if (n == 1) {
			cout<<"TAK"<<endl;
			continue;
		}

    vector<int> byTarr = sortIndexesTarr(tab, n);
    vector<int> byCurr = sortIndexesCurr(tab, n);
		double litrChild=tab[byCurr[1]].litre, tempVol=tab[byCurr[0]].litre, tempTemp=tab[byCurr[0]].currTemp;
		int indChild=1;
		bool fail = false;

		for (int j = 0; j < n; j++) {
      //cout<<tab[byCurr[j]].currTemp<<" "<<tab[byTarr[j]].tarrTemp<<endl;
      if (fail) {
        break;
      }
			if (tab[byTarr[j]].tarrTemp > tempTemp) {
				fail = true;
				break;
			}
			while ((!areSame(tab[byTarr[j]].tarrTemp, tempTemp) || !tab[byTarr[j]].litre <= tempVol) && indChild < n) {
        if (areSame(tab[byTarr[j]].tarrTemp, tempTemp)) { // licznik rowny zero
          if (areSame(tab[byCurr[indChild]].currTemp, tempTemp)) { // licznik równy zero

            tempVol += litrChild;
            indChild++;
            if (indChild < n) {
              litrChild = tab[byCurr[indChild]].litre;
            } else {
              litrChild = 0;
            }
            continue;
          } else {
            fail = true;
            break;
          }
        }

        if (tab[byTarr[j]].tarrTemp > tab[byCurr[indChild]].currTemp) {
  				fail = true;
  				break;
  			}

				double a = tempVol * (tempTemp - tab[byTarr[j]].tarrTemp) / (tab[byTarr[j]].tarrTemp - tab[byCurr[indChild]].currTemp);
				if (a < litrChild) {
					litrChild -= a;
					tempVol += a;
					tempTemp = tab[byTarr[j]].tarrTemp;
				} else {
					tempTemp = (tab[byCurr[indChild]].currTemp * litrChild + tempTemp * tempVol)/(litrChild + tempVol);
					tempVol += litrChild;
					indChild++;
					if (indChild < n) {
						litrChild = tab[byCurr[indChild]].litre;
					} else {
						litrChild = 0;
					}
				}
			}
			tempVol -= tab[byTarr[j]].litre;
		}
		if (fail) {
			cout<<"NIE"<<endl;
		} else {
			cout<<"TAK"<<endl;
		}
	}

	return 0;
}