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
// Solution to 2B_BOH
// Author: Michal Czuczman <michal.czuczman@gmail.com>
// created on Tue May 13 19:42:49 CEST 2014

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;

struct Monster {
	int position;
	int cost;
	int profit;
};

int main()
{
	ios::sync_with_stdio(false);
	int n;
	long long hearts;
	cin >> n >> hearts;

	vector<int> order;
	vector<Monster> easy_monsters;
	vector<Monster> tough_monsters;

	for(int i = 1; i <= n; ++i) {
		int d, a;
		cin >> d >> a;
		if(d < hearts && a >= d) {
			hearts += a - d;
			order.push_back(i);
		} else if(a >= d) {
			easy_monsters.push_back(Monster{i, d, a});
		} else {
			tough_monsters.push_back(Monster{i, d, a});
		}
	}

	sort(easy_monsters.begin(), easy_monsters.end(),
		[] (const Monster& a, const Monster& b) -> bool {
			return a.cost < b.cost;
		});

	for(const Monster& m: easy_monsters) {
		hearts -= m.cost;
		if(hearts <= 0) {
			cout << "NIE\n";
			return 0;
		}
		hearts += m.profit;
		order.push_back(m.position);
	}

	sort(tough_monsters.begin(), tough_monsters.end(),
		[] (const Monster& a, const Monster& b) -> bool {
			return a.cost >= b.cost;
		});

	for(const Monster& m: tough_monsters) {
		hearts -= m.cost;
		if(hearts < 0) {
			cout << "NIE\n";
			return 0;
		}
		hearts += m.profit;
		order.push_back(m.position);
	}

	cout << "TAK\n";
	int first = 1;
	for(auto position : order) {
		if(first) {
			first = 0;
		} else {
			cout << " ";
		}
		cout << position;
	}
	cout << "\n";
}