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
#include <iostream>
#include <vector>
#include <set>

const int k_size = 1000001;
int tab[k_size][2];

struct cmp
{
 bool operator()(int a, int b)
 {
   return ((tab[a][1] - tab[a][0]) >= (tab[b][1] - tab[b][0]));
 }
};

bool good = false;
std::vector<int> odpowiedz;

// pokonywanie potworow, ktore mozna w danej chwili
std::set<int, cmp> choose(int& curr_life, std::set<int, cmp> s0)
{
 std::set<int, cmp> s1; 
 int tmp_a = *(s0.begin());
 bool abort_choosing = tab[tmp_a][1] - tab[tmp_a][0] > 0;
 while (!s0.empty()) {
   int a = *(s0.begin());
   std::cout << "curr_life =  " << curr_life << '\n';
   std::cout << "a = " << a << '\n';
   s0.erase(s0.begin());
   if (curr_life > tab[a][0] && !((tab[a][1] - tab[a][0] < 0) && abort_choosing)) {
     curr_life += tab[a][1] - tab[a][0];
     odpowiedz.push_back(a);
   } else {
     s1.insert(a);
   }
 }
 return s1;
}

// symulacja walki
void fight(int curr_life, std::set<int, cmp> s)
{
 std::set<int, cmp> s1 = s;
 int ps = 0;
 do {
   ps = s1.size();
   s1 = choose(curr_life, s1);
   std::cout << curr_life << '\n';
 } while (int(s1.size()) != ps);
 if (s1.empty()) {
   good = true;
 } else {
   good = false;
 }
}

int main(void)
{
 std::ios_base::sync_with_stdio(0);
 int n = 0;
 int z = 0;
 std::cin >> n >> z;
 std::set<int, cmp> s;
 for (int i = 1; i <= n; ++i) {
   std::cin >> tab[i][0] >> tab[i][1];
   s.insert(i);
 }
 fight(z, s);
 if (good) {
   std::cout << "TAK\n";
   for (int i = 0; i < int(odpowiedz.size()); ++i) {
     std::cout << odpowiedz[i] << ' ';
   }
 } else {
   std::cout << "NIE\n";
 }
 return 0;
}