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
// Bohater.cpp : Defines the entry point for the console application.
//

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

using namespace std;

class potwor
{
public:
	int nr;
	int obrazenia; // obrazenia zadane przez potwora
	int bilans_zycia; // wartosc bonusu do zycia po walce pomniejszona o poniesione obrazenia

	potwor(int numer, int obr, int eliksir) {nr = numer; obrazenia=obr; bilans_zycia = eliksir-obr;}
};

class bohater
{
public:
	int zycie;
	bohater (int zycie_pocz) {zycie = zycie_pocz;}

	vector<int> lista_chwaly; // lista numerow potworow w kolejnosci ich pokonywania

	bool walcz(vector<potwor> & potwory)
	{
		// bohater pokonuje potwory wedlug kolejnosci w liscie
		for (vector<potwor>::iterator it = potwory.begin(); it != potwory.end(); ++it)
		{
			if (it->obrazenia >= zycie)
				return false; // walka skazana na porazke
			zycie += it->bilans_zycia; // modyfikacja zycia po walce i wypiciu eliksiru
			lista_chwaly.push_back(it->nr); // dopisanie pokonanego potwora do listy chwaly naszego bohatera
		}
		return true; // hurra! wszystkie potwory ubite!
	}
};

bool comp_dobre(const potwor & p1, const potwor & p2)
	{ return (p1.obrazenia < p2.obrazenia) || (p1.obrazenia == p2.obrazenia && p1.bilans_zycia > p2.bilans_zycia ); }

bool comp_wredne(const potwor & p1, const potwor & p2)
	{ return (p1.obrazenia > p2.obrazenia) || (p1.obrazenia == p2.obrazenia && p1.bilans_zycia > p2.bilans_zycia ); }
	

int main()
{
	int ile_potworow, zycie; 
	cin >> ile_potworow >> zycie;

	vector<potwor> potwory_dobre, potwory_wredne;

	for(int ii=0; ii<ile_potworow; ii++)
	{
		int obr, eliksir;
		cin >> obr >> eliksir;
		if (eliksir >= obr)
			potwory_dobre.push_back(potwor(ii+1, obr, eliksir));
		else
			potwory_wredne.push_back(potwor(ii+1, obr, eliksir));
	}

	// potwory dobre (bilans_zycia >= 0) i wredne (bilans_zycia < 0) posortowane zgodnie ze strategia bohatera:
	// potwory dobre - bohater pokonuje je w pierwszej kolejnosci, zeby nabic sobie jak najwyzszy poziom zycia;
	// sortowane wedlug wzrostu zadawanych obrazen - jesli bohater nie potrafi pokonac pierwszego, nie pokona tez zadnego z kolejnych; 
	// potwory wredne - sortowane wedlug malejacych obrazen i malejacych wartosci eliksirow, jesli bohater nie potrafi pokonac pierwszego 
	// (najtrudniejszego) z maksymalnym poziomem zycia, nie pokona go takze w przyszlosci, kiedy jego poziom zycia spadnie po walkach z innymi wrednymi potworami

	sort(potwory_dobre.begin(), potwory_dobre.end(), comp_dobre);
	sort(potwory_wredne.begin(), potwory_wredne.end(), comp_wredne);	

	bohater Bitor = bohater(zycie);
	bool wynik_walki = Bitor.walcz(potwory_dobre); // czy Bitorowi udalo sie pokonac potwory z listy
	if (wynik_walki == true)
		wynik_walki = Bitor.walcz(potwory_wredne);

	if (wynik_walki == false)
		cout << "NIE" <<endl;
	else
	{
		cout << "TAK" <<endl;
		for (vector<int>::iterator it = Bitor.lista_chwaly.begin(); it != Bitor.lista_chwaly.end(); ++it)
			cout<< *it << " ";
	}		

	return 0;
}