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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Monster {
	int idx;
	int hurts;
	int heals;
};
typedef vector< Monster > monsters_t;
ostream& operator<< (ostream&, monsters_t const&);

void read_data(int& health, monsters_t& M)
{
	int num_creatures;
	cin >> num_creatures >> health;
	for ( int i = 0; i < num_creatures; ++i ) {
		Monster m;
		m.idx = i + 1;
		cin >> m.hurts;
		cin >> m.heals;
		M.push_back( m );
	}
}

void prepare_fights(monsters_t& M)
{
	auto it_zero = partition ( M.begin(), M.end(), [](Monster const& m) {
		return m.heals > m.hurts;
	});

	auto it_minus = partition (it_zero, M.end(), [](Monster const& m) {
		return m.heals == m.hurts;	
	});

	sort( M.begin(), it_zero, [](Monster const& a, Monster const& b) {
		// najpierw walczymy z najlatwiejszymi; kazda walka poprawia zdrowie
		return a.hurts < b.hurts;
	});

	sort( it_minus, M.end(), [](Monster const& a, Monster const& b) {
		// to samo w grupie plus, tylko na odwrot
		return a.heals > b.heals;
	});
};

bool win(int health, monsters_t const& M)
{
	for( auto duel : M ) {
		health -= duel.hurts;
	       	if ( health <= 0 ) return false;
		health += duel.heals;
	}
	return true;
}

int main()
{
	int health;
	monsters_t M;

	read_data( health, M );
	prepare_fights( M );
	if( win(health, M ) ) {
		cout << "TAK\n";
		cout << M << endl;
	}
	else {
		cout << "NIE\n";
	}
}

ostream& operator<< (ostream& os, monsters_t const& M )
{
	for( auto const e : M ) {
		os << e.idx;
		if( e.idx != M.back().idx ) os << " ";
	}
	return os;
};