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

static const int MaxTasks = 100;

struct Task {
  int start;
  int stop;
  int end;
  Task() {}
  Task(int start, int stop, int end): start(start), stop(stop), end(end) {}
};

bool SortByStart(const Task& lhs, const Task& rhs) {
  if(lhs.start != rhs.start)
    return lhs.start < rhs.start;
  if(lhs.stop != rhs.stop)
    return lhs.stop < rhs.stop;
  return lhs.end < rhs.end;
}

bool SortByStop(const Task& lhs, const Task& rhs) {
  if(lhs.stop != rhs.stop)
    return lhs.stop < rhs.stop;
  return lhs.end < rhs.end;
}

void ReadTasks(Task* tasks, int n) {
  Task* endTasks = tasks + n;
  for(Task* task = tasks; task < endTasks; ++task) {
    int p, k, c;
    cin >> p >> k >> c;
    task->start = p;
    task->stop = p + c;
    task->end = k;
  }
  endTasks->start = 1111111;
  endTasks->stop = 2222222;
  endTasks->end = 3333333;
  sort(tasks, endTasks, SortByStart);
}

bool DeleteTasks(Task* tasks, Task* task, Task** endTasks) {
  Task* endDelete = tasks;
  int time = task->start;
  sort(tasks, task + 1, SortByStop);
  while(endDelete->stop <= time)
    ++endDelete;
  if(endDelete != tasks) {
    while(endDelete < *endTasks)
      *tasks++ = *endDelete++;
    *endTasks = tasks;
    return true;
  }
  return false;
}

bool ShiftTask(Task* tasks, Task* task, Task* endTasks) {
  //  sort(tasks, task + 1, SortByStop);
  int time = 0;
  for(Task* t = tasks; t <= task; ++t)
    if(time < t->start)
      time = t->start;
  int shift0 = task[1].start - time;        // start nie dalej niz start kolejnego zadania (m+1 zadanie)
  for(Task* t = tasks; t <= task; ++t) {
    int shift1 = t[1].stop - t->stop + 1;   // nie dalej niz o 1 za kolejnym
    int shift2 = t->end - t->stop;          // nie dalej niz koniec pola tego zadania
    if(shift2 > shift1)
      shift2 = shift1;
    if(shift2 > shift0)
      shift2 = shift0;
    if(shift2 <= 0)
      continue;
    t->start = time + shift0;
    t->stop += shift0;
    swap(*t, *task);
    for(t = task; t < endTasks && SortByStop(t[1], *t); ++t)
      swap(t[1], *t);
    return true;
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(0);
  bool good = true;
  Task tasks[MaxTasks+1];
  int n, m;

  cin >> n >> m;
  if(n <= m) {
    cout << "TAK" << endl;
    return 0;
  }
  Task* endTasks = tasks + n;
  Task* task = tasks + m;
  ReadTasks(tasks, n);

  for(; endTasks >= task; ) {
    if(DeleteTasks(tasks, task, &endTasks))
      continue;
    if(!ShiftTask(tasks, task, endTasks)) {
      cout << "NIE" << endl;
      return 0;
    }
  }
  cout << "TAK" << endl;
  return 0;
}