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

#define MAX_N 100
#define INF 2000000000

int n, m;
pair<int, int> V[MAX_N];
pair<pair<int, int>, int> V2[MAX_N];
int D[MAX_N];
int D2[MAX_N];

inline bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int> ,int> p2){
    return make_pair(p1.first.second, p1.second) < make_pair(p2.first.second, p2.second);
}

vector<int> buf;

int asd = 0;

int main(){
    scanf("%d%d", &n, &m);
    int maxK = 0;
    for(int a=0; a<n; ++a){
        scanf("%d%d%d", &V[a].first, &V[a].second, &D2[a]);
        D[a] = D2[a];
        maxK = max(maxK, V[a].second);
        V2[a].first = V[a];
        V2[a].second = a;
    }
    sort(V2, V2 + n, cmp);

label:

    int last = 0;
    while(maxK > last){

        int step = maxK - last;

        for(int b=0; b<n; ++b){
            if(D[b] != 0){
                step = min(step, D[b]);
                if(V[b].first > last)step = min(step, V[b].first - last);
                else if(D[b] < V[b].second - last)step = min(step, V[b].second - last - D[b]);
            }
        }

        buf.clear();
        for(int b=0; b<n; ++b){
            if(V[b].first <= last && D[b] != 0){
                if(D[b] == V[b].second - last){
                    buf.push_back(b);
                }
            }
        }
        if(int(buf.size()) > m){
            if(asd == 1){
                printf("NIE");
                return 0;
            }
            ++asd;
            maxK = 0;
            for(int a=0; a<n; ++a){
                V[a] = {1000000 - V[a].second, 1000000 - V[a].first};
                D[a] = D2[a];
                maxK = max(maxK, V[a].second);
                V2[a].first = V[a];
                V2[a].second = a;
            }
            sort(V2, V2 + n, cmp);
            goto label;
        }

        if(int(buf.size()) != m){
            for(int b=0; b<n; ++b){
                if(V2[b].first.first <= last && D[V2[b].second] != 0){
                    if(D[V2[b].second] != V2[b].first.second - last){
                        buf.push_back(V2[b].second);
                        if(int(buf.size()) >= m)break;
                    }
                }
            }
        }

        for(int x : buf){
            D[x] -= step;
        }


        last += step;
    }

    printf("TAK");
    return 0;
}