Cod sursa(job #442152)

Utilizator mullerMuller Robert muller Data 13 aprilie 2010 22:13:02
Problema Gutui Scor 50
Compilator c Status done
Runda teme_upb Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui {
	int h,g;
}Gutuie;

int compara_gutui (const void *X, const void *Y) {

	Gutuie G1 = *((Gutuie *)X);
	Gutuie G2 = *((Gutuie *)Y);

	if (G1.g < G2.g) {
		return 1;
	}
	else {
		if (G1.g > G2.g) {
			return -1;
		}
		else {
			if (G1.h < G2.h) {
				return 1;
			}
			else {
				if (G1.h > G2.h) {
					return -1;
				}
				else {
					return 0;
				}
			}
		}
	}
}

int main (int argc, char *argv[]) {

	FILE *fin;
	FILE *fout;

	Gutuie *G;

	int N, H, U, i;
	short int total = 0;
	short int nivel;

	if (( fin = fopen ("gutui.in", "r") ) == NULL) {
		printf ("Fisierul nu poate fi deschis!\n");
		exit(1);
	}

	if (( fout = fopen ("gutui.out", "w") ) == NULL) {
		printf ("Fisierul nu poate fi deschis!\n");
		exit(1);
	}

	fscanf(fin,"%d %d %d",&N, &H, &U);

	G = (Gutuie*) malloc (N*sizeof(Gutuie));

	for ( i = 0 ; i < N ; i++ ) {
		fscanf(fin,"%d %d",&G[i].h, &G[i].g);
	}

	qsort ((void*)G, N, sizeof(Gutuie), compara_gutui);

	int *aux;
	int k = H / U + 1;
	aux = (int*) malloc ( k*sizeof(int));
	for ( i = 0 ; i < k ; i++ )
		aux[i] = 0;
	
	for ( i = 0 ; i < N ; i++ ) {
		nivel = ((H - G[i].h) / U);
		if ( aux[nivel] == 0 ) {
			total += G[i].g;
			aux[nivel] = 1;
		}
		else {
			int k = 0;
			while ( aux[nivel] != 0 && nivel>=0 ) {
				nivel -= 1;
				if ( nivel >= 0 && aux[nivel] == 0 )
					k = 1;
			}
			if ( k == 1 ) {
				total += G[i].g;
				aux[nivel] = 1;	
			}
		}
	}

	fprintf (fout, "%d\n\n", total);

	free(G);
	free(aux);

	fclose (fin);
	fclose (fout);

	return 0;

}