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

int n_zada; //liczba zadań do wykonania	1-100
int m_proc; //liczba procesorów	1-100
//-----------------
struct opzad { //początek, koniec, czas trwania (p: 0-10^6-1; k,c: 1-10^6)
	int poczatek;
	int koniec;
	int dlugosc;
} opzad[100];
int biepocz;	//indeks następnego zadania do najbliższego włączenia

struct opzad *kolejka[100];	//kolejka zadań do przetworzenia w danym momencie czasowym
int dlkolejki;	//ilosc zadań do przetworzenia

int biezczas;

//--------------
int sortbypocz(const void *, const void *);	//sortowanie rosnące wg początku zadania
void dolzada(int pocz);	//wstawia do kolejki zadania do przetworzenia od danego momentu czasowego
int sortkolej(const void *, const void *); //sortowanie kolejki wg dlugości okienek rosnąco i czasu wykonania malejąco
void wykonaj(void);	//wykonaj zadania
void aktualizuj(void); //usun wykonane zadania
int luzy(int punktczas, struct opzad *zadanie);	//oblicza luzy czasowe dla zadania
//---------------

//*************************************
int main()
{

	int koniec = 0;	//moment zakonczenia ostatniego zadania
	int i;


	(void)scanf("%d%d", &n_zada, &m_proc);
	for(i=0; i<n_zada; i++)
	{
		(void)scanf("%d%d%d", &opzad[i].poczatek, &opzad[i].koniec, &opzad[i].dlugosc);
		koniec = koniec < opzad[i].koniec ? opzad[i].koniec : koniec;	//znajdż moment zakonczenia ostatniego zadania
	}

	qsort(opzad, n_zada, sizeof(struct opzad), sortbypocz);

//	for(int i=0; i<n; i++)
//		printf("%d %d %d\n", opzad[i].poczatek, opzad[i].koniec, opzad[i].dlugosc);

	biezczas = opzad[0].poczatek;

	while(biezczas<koniec)
	{
		dolzada(biezczas);
		qsort(kolejka, dlkolejki, sizeof(struct opzad*), sortkolej);
		//if(kolejka[0]->koniec - kolejka[0]->dlugosc - biezczas < 0)
//		printf("%d\n", luzy(biezczas, kolejka[0]));
		if(dlkolejki && (luzy(biezczas, kolejka[0])< 0) )
		{
//			printf("NIE 1 - czas: %d p:%d k:%d d:%d\n", biezczas, kolejka[0]->poczatek, kolejka[0]->koniec, kolejka[0]->dlugosc);
			printf("NIE");
			return 0;
		}
		wykonaj();
		aktualizuj();

		biezczas++;
	}

	while(dlkolejki--)
	{
		if(kolejka[dlkolejki]->dlugosc)
		{
			printf("NIE");
			return 0;
		}
	}

	printf("TAK");

	return 0;
}
//***********************************
int sortbypocz(const void *a, const void *b)
{
	//struct opzad *a_tmp = (struct opzad *)a, *b_tmp = (struct opzad *)b;

	return ((struct opzad *)a)->poczatek - ((struct opzad *)b)->poczatek;

}
//------------
void dolzada(int pocz)
{
//	for(int i=0; i<n_zada; i++)
//	{
//		if(pocz==opzad[i].poczatek)
//		{
//			kolejka[dlkolejki++] = &opzad[i];
//		}
//	}
	while(biepocz<n_zada && opzad[biepocz].poczatek==pocz)
	{
		kolejka[dlkolejki++] = &opzad[biepocz++];
	}

}
//---------------
int sortkolej(const void *a, const void *b) //sortowanie kolejki wg dlugości okienek rosnąco i czasu wykonania malejąco
{
	struct opzad *a_tmp = *(struct opzad **)a, *b_tmp = *(struct opzad **)b;

//	int a_luzy = a_tmp->koniec - a_tmp->dlugosc - biezczas;
//	int b_luzy = b_tmp->koniec - b_tmp->dlugosc - biezczas;
	int a_luzy = luzy(biezczas, a_tmp);
	int b_luzy = luzy(biezczas, b_tmp);

	if( (a_luzy < b_luzy) || ((a_luzy==b_luzy)&&(a_tmp->dlugosc>b_tmp->dlugosc)) )
	{
		return -1;
	}
	else if( (a_luzy > b_luzy) || ((a_luzy==b_luzy)&&(a_tmp->dlugosc<b_tmp->dlugosc)) )
	{
		return 1;
	}
	else
		return 0;

}
//----------------------
void wykonaj(void)
{

	int i;

	for(i=0; i<m_proc && i<dlkolejki; i++) //wykonaj zadania, jeśli całkiem wykonane usuń z kolejki
	{
		kolejka[i]->dlugosc--;
//		if(kolejka[i]->dlugosc<0)
//		if( luzy(biezczas, kolejka[i])<0 ) //???
//			printf("NIE 3");
//		if(!(kolejka[i]->dlugosc))	//zadanie całkowicie wykonane - usunąć
//		{
//			kolejka[i] = kolejka[--dlkolejki];
//		}
	}

}
//-------------------
void aktualizuj(void)
{
	int j = 0;
	int i;

	for(i=0; i<dlkolejki; i++)
	{
		if(kolejka[i]->dlugosc)	//zadanie jeszcze nie zakończone
		{
			kolejka[j] = kolejka[i];
			j++;
		}
	}
	dlkolejki = j;
}
//--------------------
int luzy(int punktczas, struct opzad *zadanie)
{
	return zadanie->koniec - zadanie->dlugosc - punktczas;
}