Cod sursa(job #435492)

Utilizator kp_itchyAlexandra kp_itchy Data 7 aprilie 2010 15:20:55
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.8 kb
#include<stdio.h>
#include<malloc.h>

typedef struct {
	int inaltime;
	int greutate;
	} gutuie;

//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
	gutuie aux;
	aux=*a;
	*a=*b;
	*b=aux;
}

//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
	return ((i+j)/2);
}

//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {	
	int key,i,j,k;
	if (m<n)
		{
			k=choose_pivot(m,n);
			swap(&g[m],&g[k]);
			key=g[m].greutate;
			i=m+1;
			j=n;
			while (i<=j)
				{
				while ((i<=n)&&(g[i].greutate>=key))
					i++;
				while ((j>=m) &&(g[j].greutate<key))
					j--;
				if (i<j)
					swap(&g[i],&g[j]);
				}
			swap(&g[m],&g[j]);
			qsort(g,m,j-1);
			qsort(g,j+1,n);
		}
	}

int main() {
	//DECLARARI VARIABILE
	int n,h,u,i,j,gt=0;
	FILE *in=fopen("gutui.in","r");
	FILE *out=fopen("gutui.out","w");
	int ordine_cules[100][100],c;
	fscanf(in,"%d",&n);
	
	//ALOCARI DE MEMORIE
	gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
	
	//CITIRE DIN FISIER SI COMPLETARE CAMPURI GUTUI	
	fscanf(in,"%d%d",&h,&u);
	for (i=0;i<n;i++)
		fscanf(in,"%d%d",&g[i].inaltime,&g[i].greutate);
	/*
	for (i=0;i<n;i++)
		printf("%d %d\n",g[i].inaltime,g[i].greutate);
	printf("\n");	
	*/
	qsort(g,0,n-1);
	/*
	for (i=0;i<n;i++)
		printf("%d %d\n",g[i].inaltime,g[i].greutate);
	printf("\n");
	
	for (i=0;i<n;i++) 
		for (j=0;j<n;j++)
			ordine_cules[i][j]=0;
	*/
	for (i=0;i<n;i++)
		{ 
		c=0;
		while (ordine_cules[(h-g[i].inaltime)/u][c]!=0) c++;
		ordine_cules[(h-g[i].inaltime)/u][c]=i+1;	
		}
	/*
	for (i=0;i<n;i++) {
		for (j=0;j<n;j++)
			printf("%d ",ordine_cules[i][j]);
		printf("\n");
		}
	*/	
	for (i=0;i<n;i++)
		for (j=0;j<=i;j++)
			if (ordine_cules[i][j]!=0)
				gt+=g[ordine_cules[i][j]-1].greutate;
	fprintf(out,"%d\n",gt);
		
	
return 0;
}