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
#include <stdio.h>

int n,m,t,dt;
char czas[1000001];

struct zad
{
	int p;
	int k;
	int dl;
	signed char akt;
};

struct zad zadania[101];

void wczytaj()
{
	int i,a,b,c;
	
	for(i=0;i<1000001;++i)
		if (i%13) czas[i]=0; else czas[i]=1;
	
	scanf("%d %d\n",&n,&m);
	
	for(i=0;i<n;++i)
	{
		scanf("%d %d %d",&a,&b,&c);
		czas[a]=1; czas[b]=1;
		zadania[i].p=a; 
		zadania[i].k=b;
		zadania[i].dl=c;
		zadania[i].akt=1;
	}
	czas[0]=1; czas[1000000]=1;
	return;
}


int pilne(void)		//zwraca indeks najpilniejszego aktywnego zadania mozliwego do wykonania od chwili t z aktualnych wpisow w tabeli zadania[0..n-1] lub -1
{
	int j,a,min=1000002;
	int b=-1;
	
	for(j=0;j<n;++j)
	{
		if (zadania[j].p<=t && zadania[j].akt==1 && zadania[j].k>t)
		{
			a=zadania[j].k-t-zadania[j].dl;
			if (min>a) {min=a; b=j;}
		}
	}
	return b;
}


void aktualizuj(int j)  		//aktualizuje komorke zadania[j] o biezace dane;  
{
	zadania[j].akt=0;	
	return;
}


void wypisz(void)
{
	int z;
	printf("czas=%d\n",t);  
	for(z=0;z<n;z++)
	{
		printf("zad[%d]: %d %d %d %d\n",z,zadania[z].p,zadania[z].k,zadania[z].dl,zadania[z].akt);
	}
	printf("\n");
	return;
}

int main()
{
	int i,j,a,l,k;
	
		
	wczytaj();
	
	j=0;
//	wypisz();	
	for(i=0;i<1000001;++i)
	{		
		if(czas[i]) 
		{
			dt=i-j;  	//tyle minelo czasu od poprzedniego kroku
			t=i; 
			
			for(l=0;l<n;++l)
				if(zadania[l].akt==0) {zadania[l].dl-=dt; zadania[l].p=i; if(zadania[l].dl<=0) zadania[l].akt=-1; else zadania[l].akt=1;}
			j=i;
			
			a=0; l=pilne();			
			while(a<m && l>=0)		//dopoki sa wolne procesory i pilne zadania
			{
				aktualizuj(l); 
				a++;
				l=pilne();
			}
			
			k=t+1; while(k<1000001 && czas[k]==0) k++; if(k>1000000) k=t;						
			for(l=0;l<n;++l)
			{
				if(zadania[l].akt==0) 
				{
						if(zadania[l].dl < k-t) czas[zadania[l].dl+t]=1; 						
				}
			}	
//			wypisz();
		}
	}
	
	k=0;
	for(i=0;i<n;++i)
		if(zadania[i].akt!=-1) k=1;
	if(k) printf("NIE"); else printf("TAK");
	
	return 0;
}