Cod sursa(job #436470)

Utilizator carbonixVictor Carbune carbonix Data 8 aprilie 2010 16:42:18
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.69 kb
#include <stdio.h>
#define interschimb(a, b) a ^= b; b ^= a; a ^= b
#define N 100000
struct {
	int h, w;
} gutui[N];

int n, hmax, u, taken[N];

void read() {
	int i;

	scanf("%d %d %d", &n, &hmax, &u);

	for ( i = 0; i < n; i++ ) {
		taken[i] = 0;
		scanf("%d %d", &gutui[i].h, &gutui[i].w);
	}
}

void sort() {
	int i, flag = 0;

	while(!flag) {
		flag = 1;

		for ( i = 0; i < n-1; i++ )
			if ( gutui[i].h < gutui[i+1].h ) {
				interschimb(gutui[i].w, gutui[i+1].w);
				interschimb(gutui[i].h, gutui[i+1].h);
		
				flag = 0;
			}
	}
}

void print() {
	int i;

	for ( i = 0; i < n; i++ )
		printf("%d %d %d %d\n", gutui[i].h, gutui[i].w, (hmax - gutui[i].h)/u, taken[i]);

}

int getNextStep( int currStep ) {
	int i = 0;

	for ( i = 0; i < n; i++ )
		if ( !taken[i] && (hmax - gutui[i].h)/u >= currStep )
			return (hmax - gutui[i].h)/u;

	return -1;
}

int selectQuince (int currStep, int nextStep) {
	int max = -1, i, quince = -1;
	
	for ( i = 0; i < n; i++ ) {
		if (!taken[i] && (hmax - gutui[i].h)/u == nextStep && max < gutui[i].w) {
			max = gutui[i].w;
			quince = i;
		}
	}
	
	return quince;
}

int main() {
	int currStep = 0, nextStep = 0, nextQuince = 0, gmax = 0;
	freopen("gutui.in", "r", stdin);
	freopen("gutui.out", "w", stdout);
	read();
	sort();

	for ( currStep = 0; currStep < n && nextQuince >= 0 && nextStep >= 0; currStep++ ) {
		nextStep = getNextStep(currStep);
		nextQuince = selectQuince(currStep, nextStep);
		
		if(nextQuince >= 0) {
			taken[nextQuince] = 1;
			gmax += gutui[nextQuince].w;
			printf("%d %d %d\n", currStep, nextStep, gutui[nextQuince].w);
		}
/* Debug stuff
		else {
			printf("%d\tno queen!\n", currStep);
		}
*/
	}		
	
//	print();
	printf("%d \n", gmax);

	return 0; 
}