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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.function.Consumer;


public class sze
{

	public static void main(String[] args)
	{
		final Scanner in = new Scanner(System.in);


		final int tasksNo = in.nextInt();
		final int processors = in.nextInt();

		final List<Task> tasks = new ArrayList<>();

		try
		{
			int minTime = Integer.MAX_VALUE;
			for (int i = 0; i < tasksNo; i++)
			{
				int start = in.nextInt();
				Task task = new Task(start, in.nextInt(), in.nextInt());
				if (minTime > 0)
				{
					minTime = Math.min(minTime, start);
				}
				tasks.add(task);
			}

			final Counter counter = new Counter(minTime, tasksNo);
			counter.addClockListeners(tasks);

			while (!tasks.isEmpty())
			{
				sortTasks(tasks, counter);
				Iterator<Task> it = tasks.iterator();
				int toUse = processors;
				while (it.hasNext() && toUse > 0)
				{
					toUse--;
					Task task = it.next();
					if (task.getMinStart() <= counter.getCount())
					{
						if (task.grantTime())
						{
							it.remove();
							counter.removeListener(task);
						}
					}
					else
					{
						break;
					}
				}
				counter.onClock();
			}

			System.out.println("TAK");

		}
		catch (final TaskDelayedException ex)
		{
			System.out.println("NIE");
		}

		System.exit(0);
	}

	private static void sortTasks(final List<Task> tasks, Counter counter)
	{
		Collections.sort(tasks, (Task o1, Task o2) -> {
			if (o1.getMaxEnd() - o1.getCost() == counter.getCount())
			{
				return -1;
			}
			else if (o2.getMaxEnd() - o2.getCost() == counter.getCount())
			{
				return 1;
			}
			else if (o1.getMaxEnd() < o2.getMaxEnd())
			{
				return -1;
			}
			else if (o1.getMaxEnd() > o2.getMaxEnd())
			{
				return 1;
			}
			return 0;
		});
	}

	private static class Counter
	{

		private int count;
		private List<Consumer<Integer>> listeners;

		public Counter(int initCounter, int listenersNo)
		{
			count = initCounter;
			listeners = new ArrayList<>(listenersNo);
		}

		public void addClockListeners(Collection<Task> consumers)
		{
			listeners.addAll(consumers);
		}

		public void removeListener(Task task)
		{
			listeners.remove(task);
		}

		public void onClock()
		{
			count++;
			listeners.stream().forEach(listener -> listener.accept(count));
		}

		public int getCount()
		{
			return count;
		}
	}

	private static class Task implements Consumer<Integer>
	{
		private int minStart;
		private int maxEnd;
		private int cost;

		public Task(int minStart, int maxEnd, int cost)
		{
			this.minStart = minStart;
			this.maxEnd = maxEnd;
			this.cost = cost;
		}

		public boolean grantTime()
		{
			cost--;
			return cost == 0;
		}

		@Override
		public void accept(final Integer currentTime)
		{
			if ((maxEnd - cost) < currentTime)
			{
				throw new TaskDelayedException();
			}
		}

		public int getMinStart()
		{
			return minStart;
		}

		public int getMaxEnd()
		{
			return maxEnd;
		}

		public int getCost()
		{
			return cost;
		}

		@Override
		public String toString()
		{
			return minStart + " : " + maxEnd + ", " + cost;
		}
	}

	private static class TaskDelayedException extends RuntimeException
	{
		// NOOP
	}

}