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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int main()
{
	int n, m;
	scanf("%d%d",&n,&m);
	int start[n], end[n], length[n];
	
	for (int i=0; i<n; i++)
		scanf("%d%d%d",&start[i],&end[i],&length[i]);
	vector<pair<float, int> > v; //zadania w trakcie użycia
	int currTime=0;
	int doneTasks = 0;
	while (true)
	{
		int nextStartTime = 1000000*100;
		for (int j=0; j<n; j++)
		{
			if (start[j] > currTime && start[j] < nextStartTime)
				nextStartTime = start[j];
			if (start[j] == currTime)
			{
				v.push_back(make_pair((float)(end[j]-start[j])/length[j], j));
			}
		}
		
		for (int j=0; j<v.size(); j++)
		{
			if (currTime >= end[v[j].second])
			{
				printf("NIE\n");
				return 0;
			}
			v[j].first = (float)(end[v[j].second]-currTime)/length[v[j].second];

			if (v[j].first < 0.99999999)
			{
				printf("NIE\n");
				return 0;
			}
		}

		sort(v.begin(), v.end());
			
		int nextEndTaskTime = 1000000*100;
		for (int j=0; j<m && j<v.size(); j++)
			if (nextEndTaskTime > currTime + length[v[j].second])
				nextEndTaskTime = currTime + length[v[j].second];
				
		int nextUtilizationChange = 1000000*100;
		//if (v.size() > m) //jest jakiś nieużywany task
		//for (int j=0; j<n; j++)
		
		int nextTime;
		if (nextStartTime < nextEndTaskTime && nextStartTime < nextUtilizationChange)
			nextTime = nextStartTime;
		else if (nextEndTaskTime < nextUtilizationChange)
			nextTime = nextEndTaskTime;
		else
			nextTime = nextUtilizationChange;
		
		nextTime = currTime + 1;
		
		vector<pair<float, int> > newV;
		int interval = nextTime - currTime;
		for (int j=0; j<v.size(); j++)
		{
			if (j<m)
				length[v[j].second] -= interval;
			if (length[v[j].second] <= 0)
				doneTasks++;
			else
				newV.push_back(v[j]);
		}
		
		v = newV;
		
		currTime = nextTime;
		
		if (doneTasks == n)
			break;
	}
	
	printf("TAK\n");
	return 0;
}