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
#include <iostream>
#include <list>

using namespace std;

class Monster {
    public: // dla wygody wszystko publiczne
    int numer;
    int dmg;
    int heal;
    int dif; // roznica heal - dmg, dla szybkosci liczona tylko raz i przechowana

    // przy ustalaniu kolejnosci ubijania potworow bedzie potrzebna mozliwosc
    // porownania damagu jaki robia, do tego przyda sie operator porownania,
    // uzywany w taki sposob: if (monster1 < monster2) ...
    bool operator<(Monster m) {
        return (dmg < m.dmg);
    }
};

/*
Na poczatku gry intuicyjnie wydaje sie rozsadnym poexpic poprzez wybieranie
takich potworow, ktore 1. sa slabe i nie zabija bohatera oraz 2. przywracaja
wiecej zycia niz zabieraja. Gdy bohater przypakuje moze sie brac za potwory
grozniejsze, starajac sie jak najdluzej zachowac jak najwiecej zycia, a wiec
najpierw za te po ubiciu ktorych odzyska jak najwieksza czesc straconego zycia.
*/

bool porownaj(const Monster& m1, const Monster& m2);
void wypisz(list<int> * kolejnosc_potworow);
bool rozwiaz(list<Monster> * potwory_do_expienia,
            list<Monster> * potwory_neutralne,
            list<Monster> * potwory_grozne,
            list<int> * kolejnosc_potworow,
            int z);

int main()
{
    // struktury danych
    int n, z, di, ai, dh;
    list<Monster> * potwory_do_expienia = new list<Monster>();
    list<Monster> * potwory_neutralne = new list<Monster>();
    list<Monster> * potwory_grozne = new list<Monster>();
    list<int> * kolejnosc_potworow = new list<int>;

    // wczytaj dane
    cin >> n;
    cin >> z;

    for (int i=1 ; i<=n ; i++) {
        cin >> di, cin >> ai;
        dh = ai - di;
        if (dh > 0) {
            potwory_do_expienia->push_back({i, di, ai, dh});
        } else if (dh == 0) {
            potwory_neutralne->push_back({i, di, ai, dh});
        } else {
            potwory_grozne->push_back({i, di, ai, dh});
        }
    }

    // posortuj potwory od najslabszego do najsilniejszego
    // podzial potworow na mniejsze zbiory przyspiesza nieco ten etap

    // potwory do expienia sortujemy po damagu, poslugujac sie operatorem <
    potwory_do_expienia->sort();
    // potwory grozne sortujemy po roznicy heal - dmg, korzystajac z pomocniczej funkcji
    potwory_grozne->sort(); // szybki
    potwory_grozne->reverse(); // fix
    potwory_grozne->sort(porownaj);
    // potworow neutralnych nie trzeba sortowac, kolejnosc ich ubijania jest nieistotna

    if (rozwiaz(potwory_do_expienia,
            potwory_neutralne,
            potwory_grozne,
            kolejnosc_potworow,
            z) == true) {
        // jesli udalo sie przezyc
        wypisz(kolejnosc_potworow);
    } else {
        // jesli bohater polegl
        cout << "NIE" << endl;
    }

    return 0;
}

// funkcja przyjmuje wskazniki do list, co oznacza ze sa one modyfikowalne
bool rozwiaz(list<Monster> * potwory_do_expienia,
            list<Monster> * potwory_neutralne,
            list<Monster> * potwory_grozne,
            list<int> * kolejnosc_potworow,
            int z) {

    // czas poexpic - co nie zabije to wzmocni
    for (list<Monster>::iterator it=potwory_do_expienia->begin() ; it != potwory_do_expienia->end() ; ++it) {
        if (it->dmg >= z) {
            return false;
        } else {
            z += it->dif;
            kolejnosc_potworow->push_back(it->numer);
        }
    }

    // powybijac potwory neutralne
    for (list<Monster>::iterator it=potwory_neutralne->begin() ; it != potwory_neutralne->end() ; ++it) {
        if (it->dmg >= z) {
            return false;
        } else {
            kolejnosc_potworow->push_back(it->numer);
        }
    }

    // na koniec potwory ktore nie przywracaja calego zabranego zycia
    for (list<Monster>::iterator it=potwory_grozne->begin() ; it != potwory_grozne->end() ; ++it) {
        if (it->dmg >= z) {
            return false;
        } else {
            z += it->dif;
            kolejnosc_potworow->push_back(it->numer);
        }
    }
    
    return true;
}

void wypisz(list<int> * kolejnosc_potworow) {
    cout << "TAK" << endl;
    list<int>::iterator ostatni = kolejnosc_potworow->end();
    ostatni--;
    for (list<int>::iterator it=kolejnosc_potworow->begin() ; it != kolejnosc_potworow->end() ; ++it) {
        cout << *it;
        if (it != ostatni)
            cout << " ";
    }
    cout << endl;
}

bool porownaj(const Monster& m1, const Monster& m2) {
    return (m1.dif < m2.dif);
}