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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <vector>
#include <stdio.h>
#include <algorithm>


//#define READ_FROM_FILE

using namespace std;
#ifdef READ_FROM_FILE
#include <iostream>
#include <fstream>
#endif // READ_FROM_FILE

struct Monster
{
	int index;
	int damage;
	int heal;
};

bool sortMonsters( const Monster & m1, const Monster & m2 )
{
	int m1Bonus = m1.heal - m1.damage;
	int m2Bonus = m2.heal - m2.damage;

	if ( m1Bonus >= 0 && m2Bonus < 0 )
		return true;
	if ( m1Bonus < 0 && m2Bonus >= 0 )
		return false;
	if ( m1Bonus >= 0 && m2Bonus >= 0 )
		return m1.damage < m2.damage;
	if ( m1Bonus < 0 && m2Bonus < 0 )
	{
		return m1.damage > m2.damage;
	}
	return true;
}
bool secSort( const Monster & m1, const Monster & m2 )
{
	int m1Bonus = m1.heal - m1.damage;
	int m2Bonus = m2.heal - m2.damage;
	return m1Bonus > m2Bonus;
}

int main( )
{
#ifdef READ_FROM_FILE
	clock_t start = clock();
#endif

	int monsQ;
	int heroHealth;

#ifdef READ_FROM_FILE
	std::ifstream fin ( "sample_boh.txt" );
	//std::ifstream fin ( "data.txt" );

	if ( !fin.is_open( ) )
	{
		std::cout << "No data file" << std::endl;
		return 0;
	}
#endif // READ_FROM_FILE

#ifdef READ_FROM_FILE
	fin >> monsQ >> heroHealth;
#else
	scanf( "%d %d", &monsQ, &heroHealth );
#endif

	vector< Monster > monsters( monsQ );

	for ( int i=0; i<monsQ; ++i )
	{
#ifdef READ_FROM_FILE
		fin >> monsters[i].damage >> monsters[i].heal;
#else
		scanf( "%d %d", &monsters[i].damage, &monsters[i].heal );
#endif
		monsters[i].index = i+1;
	}
	sort( monsters.begin( ), monsters.end( ), sortMonsters );

	int stopIndex = -1;
	bool failed = false;
	for ( int i=0; i<monsQ; ++i )
	{
		if ( monsters[i].heal < monsters[i].damage )
		{
			stopIndex = i;
			break;
		}

		if ( heroHealth - monsters[i].damage < 1 )
		{
			failed = true;
			break;
		}
		heroHealth -= monsters[i].damage;
		heroHealth += monsters[i].heal;
	}

	if ( !failed && stopIndex >= 0 )
	{
		int tempHeroHealth = heroHealth;
		for ( int i=stopIndex; i<monsQ; ++i )
		{
			if ( heroHealth - monsters[i].damage < 1 )
			{
				failed = true;
				break;
			}
			heroHealth -= monsters[i].damage;
			heroHealth += monsters[i].heal;
		}
		if ( failed )
		{
			failed = false;
			sort( monsters.begin( ) + stopIndex, monsters.end( ), secSort );
			heroHealth = tempHeroHealth;

			for ( int i=stopIndex; i<monsQ; ++i )
			{
				if ( heroHealth - monsters[i].damage < 1 )
				{
					failed = true;
					break;
				}
				heroHealth -= monsters[i].damage;
				heroHealth += monsters[i].heal;
			}
		}
	}

	if ( failed )
	{
		printf( "NIE\n" );
	}
	else
	{
		printf( "TAK\n" );
		for ( int i=0; i<monsQ; ++i )
			printf( "%d ", monsters[i].index );
		printf( "\n" );
	}


#ifdef	READ_FROM_FILE
	clock_t end = clock();
	float seconds = (float)(end - start) / CLOCKS_PER_SEC;

	printf( "time - %f\n", seconds);
#endif

	return 0;
}