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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define forv(na,it) for(__typeof(na.begin()) it=na.begin(); it!=na.end(); it++)
struct zadania {
	int x, p, k;
}p[102];
bool operator < (zadania a, zadania b)
	{
	return a.p<b.p;
	}
struct wp {
	int ro, k, zos;
};
bool operator < (wp a, wp b)
	{
	if (a.ro!=b.ro) return a.ro<b.ro;
	return a.k>b.k;
	}
wp make_wp (int ro, int k, int zos)
	{
	wp pom;
	pom.ro=ro; pom.k=k; pom.zos=zos;
	return pom;
	}
int main ()
{
vector <wp> v;
int n, k, mx=0, suma=0;
scanf ("%d%d", &n, &k);
for (int i=0; i<n; i++)
	{
	scanf ("%d%d%d", &p[i].p, &p[i].k, &p[i].x);
	mx=max(mx, p[i].k);
	suma+=p[i].x;
	}
if (k>=n)
	{
	printf ("TAK");
	return 0;
	}
sort (p, p+n);
if ((mx-p[0].p)*k<suma)
	{
	printf ("NIE");
	return 0;
	}
int wskbierz=0, dl, pocz, kon;
//printf ("brut\n");
for (int i=p[0].p; i<=mx; i++)
	{
	//printf ("sekund : %d ", i);
	if (!v.empty()) for (int j=0; j<v.size();)
		{
		if (v[j].zos<=0)
			{
			v.erase(v.begin()+j);
			}
		else if (v[j].k==i)
			{
			printf ("NIE");
			return 0;
			}
		else
			j++;
		}
	while (wskbierz<n && p[wskbierz].p==i)
		{
		v.push_back(make_wp(p[wskbierz].k-p[wskbierz].p-p[wskbierz].x, p[wskbierz].k, p[wskbierz].x));
		wskbierz++;
		sort (v.begin(), v.end());
		}
	//forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n");
	dl=min(k, (int)v.size());
	for (int j=0; j<dl; j++)
		v[j].zos--;
	if (k<v.size()) for (int j=k; j<v.size(); j++)
		{
		v[j].ro--;
		if (v[j].ro<0)
			{
			printf ("NIE");
			return 0;
			}
		}
	
	//printf ("przed : "); forv(v, it) printf ("%d ", it->ro); printf ("\n");
	//sort (v.begin(), v.end());
	if (k<v.size())
		{
		for (kon=k; kon<v.size();kon++)
			if (v[k-1].ro<=v[kon].ro)
				break;
		for (pocz=k-1; pocz>=0;pocz--)
			if (v[pocz].ro<=v[k].ro)
				break;
		kon--; pocz++;
		reverse (v.begin()+pocz, v.begin()+k);
		reverse (v.begin()+k, v.begin()+kon+1);
		reverse (v.begin()+pocz, v.begin()+kon+1);
		}
	//printf ("po : "); forv(v, it) printf ("%d ", it->ro); printf ("\n");
	//forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n");
	//forv(v, it) printf ("%d ", it->k);
	}
printf ("TAK");
return 0;
}