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
117
118
119
// Solution to 5SZE
// Author: Michal Czuczman <michal.czuczman@gmail.com>
// created on Sat Nov 26 05:18:34 CET 2016

#include <algorithm>
#include <assert.h>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;

struct Task {
	int begin, end, size;

	Task() {}
	Task(int begin_, int end_, int size_)
		: begin(begin_), end(end_), size(size_) {}

	int margin() const { return end - begin - size; }
	void done(int from, int to) {
		if(from < begin) {
			from = begin;
		}
		if(to > end) {
			to = end;
		}
		if(from < to) {
			size -= to - from;
			assert(size >= 0);
			if(size == 0) {
				begin = INT_MAX;
				end = INT_MAX;
			} else {
				begin = to;
			}
		}
	}
	bool is_valid() const {
		return size <= end - begin;
	}
};

istream& operator>>(istream& is, Task& t) {
	return cin >> t.begin >> t.end >> t.size;
}

bool operator<(const Task& t1, const Task& t2) {
	if(t1.begin < t2.begin) {
		return true;
	} else if(t1.begin == t2.begin) {
		return t1.end < t2.end;
	} else {
		return false;
	}
}

int main() {
	ios::sync_with_stdio(false);

	/*
	assert(Task(0, 2, 2) < Task(0, 3, 1));
	assert(Task(0, 2, 1) < Task(0, 3, 2));
	assert(Task(0, 4, 2) < Task(1, 3, 2));
	assert(Task(0, 3, 1) < Task(0, 4, 3));
	*/

	int num_tasks, num_cpu;
	cin >> num_tasks >> num_cpu;

	vector<Task> tasks;
	tasks.reserve(num_tasks);

	for(int i = 0; i < num_tasks; ++i) {
		Task t;
		cin >> t;
		tasks.push_back(t);
	}

	while(1) {
		sort(&tasks[0], &tasks[num_tasks]);
		while(num_tasks > 0 && tasks[num_tasks - 1].size == 0) {
			--num_tasks;
		}
		if(num_tasks == 0) {
			break;
		}

		int now = tasks[0].begin;
		int next = now + tasks[0].size;
		for(int i = 1; i < num_tasks; ++i) {
			int b = tasks[i].begin;
			if(b > now && b < next) {
				next = b;
			}
			int c = b + tasks[i].size;
			if(c < next) {
				next = c;
			}
		}

		for(int i = 0; i < num_tasks; ++i) {
			if(i < num_cpu) {
				tasks[i].done(now, next);
			} else {
				tasks[i].begin = next;
			}
			if(!tasks[i].is_valid()) {
				cout << "NIE\n";
				return 0;
			}
		}
	}
	cout << "TAK\n";
	return 0;
}