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
#include <cstdio>
#include <vector>
#include <algorithm>
typedef int I;

struct Item {
        I p;
        I k;
        I c;
        I x;
        bool in(I t) const { return p <= t && t < k && c > 0; }
        bool nofree() const { return k - p - c - x <= 0; }
};

typedef std::vector<Item> VI;
typedef std::vector<I> VS;

struct CmpByEnd {
        bool operator()(const Item& a, const Item&b) {
                return a.k < b.k;
        }
};

static bool cleannofree(VI& v, VS& slots) {
        for (;;) {
                bool again = false;
                for (Item& i : v) {
                        if (i.nofree()) {
                                i.c = 0;
                                for (I t=i.p; t<i.k; ++t) {
                                        if (slots[t] == 0) {
                                                if (i.x == 0) {
                                                        return false;
                                                }
                                                --i.x;
                                                continue;
                                        }
                                        --slots[t];
                                        if (slots[t] == 0) {
                                                for (Item& u : v) {
                                                        if (u.in(t) && !u.nofree()) {
                                                                ++u.x;
                                                        }
                                                }
                                        }
                                }
                                again = true;
                                break;
                        }
                }
                if (!again)
                        return true;
        }
}

static bool process(VI& v, const I m) {
        std::sort(v.begin(), v.end(), CmpByEnd());
        I tend = v[v.size() - 1].k;
        I tstart = tend;
        for (Item& i : v) {
                if (i.p < tstart)
                        tstart = i.p;
        }

        VS slots;
        slots.resize(tend, m);
        if (!cleannofree(v, slots))
                return false;
        for (I t=tstart; t<tend; ++t) {
                bool needclean = false;
                for (Item& i : v) {
                        if (i.in(t)) {
                                if (slots[t]) {
                                        --i.c;
                                        ++i.p;
                                        --slots[t];
                                } else {
                                        ++i.p;
                                        if (i.nofree())
                                                needclean = true;
                                }
                        }
                }
                if (needclean && !cleannofree(v, slots))
                        return false;
        }
        return true;
}

int main() {
        I N, M, p, k, c;
        scanf("%d %d\n", &N, &M);
        VI v;
        for (I n=0; n<N; ++n) {
                scanf("%d %d %d\n", &p, &k, &c);
                v.push_back(Item{p, k, c, 0});
        }
        printf("%s\n", process(v, M)?"TAK":"NIE");
        return 0;
}