Cod sursa(job #463196)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 19:11:42
Problema Gutui Scor 70
Compilator c Status done
Runda teme_upb Marime 1.66 kb
#include<stdio.h>
#include<stdlib.h>

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

void quickSort1(gutui *vect, int stanga, int dreapta) {  
	int i = stanga, j = dreapta;  
	int tmp1, tmp2, tmp3;  
	int pivot = vect[dreapta].niv;  
	while (i <= j){  
		while (vect[i].niv < pivot)  
			i++;  
		while (vect[j].niv > pivot)  
			j--;  
		if (i <= j){
            tmp1=vect[i].niv;  
			vect[i].niv=vect[j].niv;  
			vect[j].niv=tmp1;
			tmp2=vect[i].h;  
			vect[i].h=vect[j].h;  
			vect[j].h=tmp2;
			tmp3=vect[i].g;  
			vect[i].g=vect[j].g;  
			vect[j].g=tmp3;
            i++;  
            j--;  
			}  
		}  
	if (stanga < j)  
		quickSort1(vect, stanga, j);  
	if (i < dreapta)  
		quickSort1(vect, i, dreapta);  
}

int main(){
	int n, h, u, i, j, k, *a, suma=0, t, dim=0, min;
	gutui *gut;
	
	//citire
	FILE *fo, *fc;
	fo=fopen("gutui.in", "r");
	fscanf(fo,"%d%d%d", &n, &h, &u);
	gut=(gutui*)malloc(n*sizeof(gutui));
	a=(int*)malloc(n*sizeof(int));
	
	for(i=0;i<n;i++){
		fscanf(fo,"%d%d", &gut[i].h, &gut[i].g);
		gut[i].niv=(h-gut[i].h)/u+1;
		if(gut[i].h>h || gut[i].h<0)
			gut[i].niv=0;	
		}
	fclose(fo);
	
	//sortare dupa nivelul fata de h maxim
	quickSort1(gut,0,n-1);
	
	//creare vector cu elemnte maxime (care reprezenta greutatea finala) 
	dim=0;
	t=0;
	k=0;
	for(i=0;i<n;i++){
		if(dim<gut[i].niv){
			a[dim]=gut[i].g;
			dim++;
			}
		else{
			min=a[0];
			for(j=0;j<dim;j++)
				if(min>a[j]){
					min=a[j];
					t=j;
					}		
			if(min<gut[i].g)
				a[t]=gut[i].g;
			}
		}
	
	//calcul suma
	for(i=0;i<dim;i++)
		suma=suma+a[i];
	
	//scriere in fisier
	fc=fopen("gutui.out", "w");
	fprintf(fc,"%d\n",suma);
	fclose(fc);
	
	//eliberare memorie
	free(gut);
	free(a);

	return 0;	
	}