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
/*************************************************************************
 *                                                                       *
 *                   Potyczki Algorytmiczne 2014                         *
 *                                                                       *
 *                  Zadanie:           Bohater [B]                       *
 *                  Autor:             Jakub Sroka                       *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class monster {
public:
    int dmg;
    int potion;
    int nr;
};

bool sortDMG(monster a, monster b) { return a.dmg < b.dmg; }
bool sortPOT(monster a, monster b) { return a.potion > b.potion; }

int main(int argc, const char * argv[])
{
    int n, hp;
    scanf("%d %d", &n, &hp);
    
    vector<monster> monsters(n);
    vector<monster> nonNegativeMonsters;
    vector<monster> negativeMonsters;
    vector<monster> negativeMonstersDMG;
    vector<int> result;
    vector<bool> isDead(n+1);
    
    for (int i=0; i<n; i++) {
        monsters[i].nr = i+1;
        scanf("%d %d", &monsters[i].dmg, &monsters[i].potion);
    }
    
    for (int i=0; i<n; i++) {
        if (monsters[i].potion-monsters[i].dmg >= 0) {
            nonNegativeMonsters.push_back(monsters[i]);
        }
        else negativeMonsters.push_back(monsters[i]);
    }
    
    sort(nonNegativeMonsters.begin(), nonNegativeMonsters.end(), sortDMG);
    for (int i=0; i<nonNegativeMonsters.size(); i++) {
        hp -= nonNegativeMonsters[i].dmg;
        if (hp <= 0) {
            printf("NIE");
            return 0;
        }
        hp += nonNegativeMonsters[i].potion;
        result.push_back(nonNegativeMonsters[i].nr);
    }
    
    sort(negativeMonsters.begin(), negativeMonsters.end(), sortPOT);
    
    int x = negativeMonsters.size();
    for (int i=0; i<x; i++) {
        result.push_back(negativeMonsters[i].nr);
        hp -= negativeMonsters[i].dmg;
        if (hp <= 0) {
            printf("NIE");
            return 0;
        }
        hp += negativeMonsters[i].potion;
    }
    
    printf("TAK\n");
    for (int i=0; i<n; i++) {
        printf("%d ", result[i]);
    }
    
    return 0;
}