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
#include <stdio.h>
#define MAX 100002
int main()
{
	struct potwor
	{
		long d;
		long a;
		float rate;
		bool used;
	};

	long n,z;
	scanf("%ld %ld",&n,&z);
	potwor tab[MAX];
	long kolejnosc[MAX];

	for (long i = 0; i < n; ++i)
	{
		scanf("%ld %ld",&tab[i].d,&tab[i].a);
		tab[i].rate=(float)tab[i].a/(float)tab[i].d;
		tab[i].used=false;
	}
	tab[MAX].d=-1;
	tab[MAX].a=-1;
	
	//-- WCZYTALIŚMY WSZYSTKIE DANE --//	

	for (long i=0;i<n;i++)
	{
		long naj=MAX;
		for (long j = 0; j < n; ++j)
		{

			//printf("j: %ld tab[j].rate:%f tab[naj].rate:%f tab[j].d:%ld\n",j,tab[j].rate,tab[naj].rate,tab[j].d);
			if (tab[j].d > tab[naj].d && tab[j].d < z && tab[j].used==false)
			{
				naj=j;
			}
			if (tab[j].d == tab[naj].d && tab[j].d < z && tab[j].used==false && tab[j].rate > tab[naj].rate)
			{
				naj=j;
			}
		}
		if(naj==MAX)
		{
			printf("NIE\n");
			return 0;
		}
		z=z-tab[naj].d;
		z=z+tab[naj].a;
		tab[naj].used=true;
		kolejnosc[i]=naj;
	}

	printf("TAK\n");
	for (int i = 0; i < n; ++i)
	{
		printf("%ld ",kolejnosc[i]+1);
	}
}