Cod sursa(job #436436)

Utilizator ana.ionana ion ana.ion Data 8 aprilie 2010 16:21:28
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.08 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
	unsigned int ht;
	unsigned int wt;
} fruct;
long h;
int compare ( const void * a, const void * b){
	fruct f1, f2;
	f1 = *(fruct*)a;
	f2 = *(fruct*)b;
	return ((h*f1.ht)/f1.wt-(h*f2.wt)/f2.wt);
}
int main (){
	FILE * fin = fopen ( "gutui.in", "r");
	FILE * fout = fopen ( "gutui.out", "w");
	long n, u;
	int i;
	fruct vec[100000];
	fscanf( fin, "%ld", &n);
	fscanf( fin, "%ld", &h);
	fscanf( fin, "%ld", &u);
	for ( i=0; i<n; i++ ){
		fscanf (fin, "%d%d", &vec[i].ht, &vec[i].wt);
	}
	i=0;
	unsigned int prada = 0, found;
	int gata =0, j;
	while ( (h>=0) && (gata==0) ){
		qsort(vec, n, sizeof(fruct), compare);
		found=0;
		while ( (found==0) && (i<n) ){
			if ( vec[i].ht<=h ){
				j=i;
				/*while ( vec[i].ht==vec[j].ht ){
					if ( vec[j].wt>vec[i].wt ){
						aux=vec[i].wt;
						vec[i].wt=vec[j].wt;
						vec[j].wt=aux;	
					}
					j++;
				}*/
				found=1;
			}
			i++;
		}
		if ( found==1 ){
			prada = prada + vec[i-1].wt;
			h = h-u;
		}
		else
			gata=1;
	}
	fprintf (fout,"%d\n", prada);
	fclose ( fin );
	fclose ( fout );
	return 0;
}