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
#include <cstdio>
#include <set>
using namespace std;

const int MAX=1000001;
class A {
        public:
        int p, c, id;
        A(int p, int c, int id): p(p), c(c), id(id) {};
        A() {};
};
class S {
        public:
        bool operator() (const A &f, const A &s)
        {
                if (f.c + f.p > s.p + s.c) return true;
                if (f.c + f.p < s.p + s.c) return false;
                if(f.id < s.id) return true;
                return false;
        }
};

set<A, S> t[MAX];
int main()
{
        int n, M;
        scanf("%d %d", &n, &M);
        int p, k, c;
        int max=0;
        for (int i = 0; i < n; i++)
        {
                scanf("%d %d %d", &p, &k, &c);
                A a;
                a.p = p;
                a.c = c;
                a.id = i;
                t[k].insert(a);
                if (k > max) max = k;
        }
        set<A, S>::iterator dit;
        for (int i = max; i > 0; i--)
        {
                int m=0;
                if (t[i].empty()) continue;
                for (set<A, S>::iterator it = t[i].begin() ;  it != t[i].end(); m++)
                {
                        A a(it->p, it->c, it->id);
                        if ( m < M) a.c--;  // jest obslugiwany przez procesor
                        if (a.c > 0 && a.c < i-a.p)  t[i-1].insert(a);  // cos 
			if (a.c > 0 && a.c>=i-a.p){ printf("NIE"); return 0; }		 	
                        dit=it;
                        ++it;
                        t[i].erase(dit);
                }
        }
        if (! t[0].empty())
        {
                printf("NIE");
        }
        else
                printf("TAK");
        return 0;
}