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
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long           ll;
typedef unsigned long long ull;
typedef unsigned int      uint;

const int Max = 1000000+1;
ll objetosc[Max+3];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  do {
    fill_n(objetosc + 1, Max, 0);
    objetosc[Max+1] = -1;            // ograniczniki
    objetosc[Max+2] = 1;
    bool wynik = false;
    int n, iMniejsze = 1, iKubek = 1;
    ll roznicaEnergii = 0;//, pozostalaObjetosc = 0;
    double objetoscLewa = 0, objetoscPrawa = 0, objetoscKubka = 0;
    double energiaLewa = 0, energiaPrawa = 0, energiaKubka = 0;
    double tempKubka, tempLewa, tempPrawa;
    cin >> n;
    for(int i = 0, l, a, b; i < n; ++i) {
      cin >> l >> a >> b;
//      pozostalaObjetosc += l;
      objetoscPrawa += l;
      roznicaEnergii += (a - b) * l;
      energiaPrawa += a * l;
      objetosc[a] += l;
      objetosc[b] -= l;
    }

    if(roznicaEnergii != 0) {
      cout << "NIE" << endl;
      continue;;
    }

    while(!wynik) {
      while(0 <= objetosc[iMniejsze]) {
        if(0 < objetosc[iMniejsze]) {
            ll tmp = objetosc[iMniejsze] * iMniejsze;
            energiaLewa += tmp;
            energiaPrawa -= tmp;
            objetoscLewa += objetosc[iMniejsze];
            objetoscPrawa -= objetosc[iMniejsze];
        }
        ++iMniejsze;
      }
      if(Max < iMniejsze || objetoscLewa < 1.0e-20)
        break;
      iKubek = iMniejsze;
      objetoscKubka = 0;
      energiaKubka = 0;
      while(0 >= objetosc[iKubek]) {
        if(0 > objetosc[iKubek]) {
          energiaKubka -= objetosc[iKubek] * iKubek;
          objetoscKubka -= objetosc[iKubek];
//          pozostalaObjetosc += objetosc[iKubek];
        }
        ++iKubek;
      }
      if(Max < iKubek)
        break;
      tempKubka = energiaKubka / objetoscKubka;
      tempLewa = energiaLewa / objetoscLewa;
      tempPrawa = energiaPrawa / objetoscPrawa;
      double objLewa = (tempKubka - tempPrawa) / (tempLewa - tempPrawa) * objetoscKubka;
      if(objLewa > objetoscLewa)
        break;
      objetoscLewa -= objLewa;
      objetoscPrawa -= objetoscKubka - objLewa;
      energiaLewa -= objLewa * tempLewa;
      energiaPrawa -= (objetoscKubka - objLewa) * tempPrawa;
      if(energiaPrawa < 1.0e-20)//(pozostalaObjetosc == 0)
        wynik = true;
    }

    cout << (wynik ? "TAK": "NIE") << endl;
  } while(--t > 0);

  return 0;
}