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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<iostream>
#include<stdlib.h>
#include<stdint.h>
#include<vector>
#include<string>
#include<bitset>
#include<algorithm>

using namespace std;

#define DEBUG
#define ASSERT

#ifdef DEBUG
#define ifdebug if(true)
#else
#define ifdebug if(false)
#endif

#ifdef ASSERT
#define ifassert if(true)
#else
#define ifassert if(false)
#endif

/// Klasa z informacją o zadaniu
class Task {
public:
	int p;
	int k;
	int c;
	int c2;
};

int n;				/// liczba zadań
Task task[100];	/// wszystkie zadania
int cpus;			/// liczba procesrów
int timeMin;		/// najmniejszy czas rozpoczęcia zadania
int timeMax;		/// największy czas zakończenia zadania

int currentTime;

bool taskPriorityFunc(const Task* t1, const Task* t2) {
	return  ((currentTime - t1->p) - t1->c) < ( (currentTime - t2->p ) - t2->c);
}

bool taskPriorityFunc2(const Task* t1, const Task* t2) {
	return  (t1->k - t1->c2) < (t2->k - t2->c2);
}

/// Informacja o danym momencie czasu
class TimeMoment {
public:
	bitset<100> tasks;		/// zadania do wykonania w danym czasie
	int count;				/// liczba zadań dla danego czasu
	bool starts;			/// czy coś się w tym czasie zaczyna
	bool ends;				/// czy coś się w tym czasie kończy
public:
	TimeMoment() { count=0; starts=false; ends=false; }
public:
	void assign(int taskNr) {
		++count;
		tasks[taskNr]=true;
	}
};

TimeMoment moment[1000001];	/// informacja o czasie
vector<Task*> processing;

int main(int argc, char** argv) {
	std::ios::sync_with_stdio(false);	// przyspieszenie wejścia/wyjścia

	// odczyt danych
	cin>>n>>cpus;

	timeMin=1000000;
	timeMax=0;

	for(int i=0;i<1000001;++i) {
		if(moment[i].starts || moment[i].ends) throw "Ble";
	}

	for(int i=0;i<n;++i) {
		Task& t=task[i];
		cin>>t.p>>t.k>>t.c;
		t.c2=t.c;
		if(timeMin>t.p) timeMin=t.p;	// aktualizacja czasu początkowego
		if(timeMax<t.k) timeMax=t.k;	// aktualizacja czasu końcowego
		moment[t.p].starts|=true;
		moment[t.k].ends|=true;
	}

	bool valid=true;

	for(currentTime=timeMax;currentTime>timeMin;--currentTime) {
		if(moment[currentTime].ends) {
			bool changed=false;
			for(int i=0;i<n;++i) {
				if(task[i].k==currentTime) {
					processing.push_back(&task[i]);
					changed=true;
				}
			}
			if(changed) sort(processing.begin(), processing.end(), taskPriorityFunc);
		}
		{
			int c=cpus;
			bool changed=false;
			for(int i=0;i<processing.size() && c>0;++i) {
				Task* t=processing[i];
				if(t->p>(currentTime-t->c)) {
					valid=false;
					break;
				}
				--c;
				if(--t->c==0) {
					processing.erase(processing.begin()+i);
					changed=true;
					--i;
				}
			}
			if(!valid) break;
			if(changed) sort(processing.begin(), processing.end(), taskPriorityFunc);
		}
	}
	if(valid && processing.size()==0) {
		cout<<"TAK"<<endl;
		return 0;
	}

	valid=true;
	processing.clear();
	for(int currentTime=timeMin;currentTime<=timeMax;++currentTime) {
		if(moment[currentTime].starts) {
			bool changed=false;
			for(int i=0;i<n;++i) {
				if(task[i].p==currentTime) {
					processing.push_back(&task[i]);
					changed=true;
				}
			}
			if(changed) sort(processing.begin(), processing.end(), taskPriorityFunc2);
		}
		{
			int c=cpus;
			bool changed=false;
			for(int i=0;i<processing.size() && c>0;++i) {
				Task* t=processing[i];
				if(t->k<(currentTime+t->c)) {
					valid=false;
					break;
				}
				--c;
				if(--t->c2==0) {
					processing.erase(processing.begin()+i);
					changed=true;
					--i;
				}
			}
			if(!valid) break;
			if(changed) sort(processing.begin(), processing.end(), taskPriorityFunc2);
		}
	}
	if(valid && processing.size()==0) {
		cout<<"TAK"<<endl;
		return 0;
	}
	else cout<<"NIE"<<endl;

	return 0;
}