Cod sursa(job #436774)

Utilizator kp_itchyAlexandra kp_itchy Data 8 aprilie 2010 23:04:55
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 3.48 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);
		}
	}
	
void merge	(int *ind, int *ord, int *c, int *d, int low, int high, int mid);
void mergesort(int *ind, int * ord, int *c, int *d, int low, int high) {
	int mid;
	if	(low<high)
		{
		mid=(low+high)/2;
		mergesort(ind, ord, c,d,low, mid);
		mergesort(ind, ord, c,d,mid+1, high);
		merge(ind, ord, c,d,low, high, mid);
		}
	return;
	}
	
void merge(int *ind, int *ord, int *c, int *d, int low, int high, int mid) {
	int i,j,k;
	i=low;
	j=mid+1;
	k=low;
	while((i<=mid)&&(j<=high))
		{
			if (ord[i]<=ord[j])
				{
					c[k]=ord[i];
					d[k]=ind[i];
					k++;
					i++;
				}
			else
				{
					c[k]=ord[j];
					d[k]=ind[j];
					k++;
					j++;
				}
		}
	while (i<=mid)
		{
		c[k]=ord[i];
		d[k]=ind[i];
		k++;
		i++;
		}
	while (j<=high)
		{
		c[k]=ord[j];
		d[k]=ind[j];
		k++;
		j++;
		}
	for (i=low;i<k;i++) {
		ord[i]=c[i];
		ind[i]=d[i];
		}
	}
	
	
int main() {
	//DECLARARI VARIABILE
	int n,h,u,i,gt=0,acc,inplus;
	FILE *in=fopen("gutui.in","r");
	FILE *out=fopen("gutui.out","w");
	
	fscanf(in,"%d",&n);
	
	//ALOCARI DE MEMORIE
	gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
	int *ord=(int*)malloc(n*sizeof(int));
	int *ind=(int*)malloc(n*sizeof(int));
	int *c=(int*)malloc(n*sizeof(int));	
	int *d=(int*)malloc(n*sizeof(int));		
	
	//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");
	*/
	int hmax=0,hmin=g[0].inaltime;
	for (i=0;i<n;i++) {
		if (g[i].inaltime>hmax) hmax=g[i].inaltime;
		if (g[i].inaltime<hmin) hmin=g[i].inaltime;
	}
		
	acc=(h-hmin)/u+1;
	//VARIANTA 1
	/*
	//formez vectorii ind si ord	
	for (i=0;i<n;i++) {
		ind[i]=i;
		if (g[i].inaltime>h)
			ord[i]=-1;
		else
			ord[i]=(h-g[i].inaltime)/u;
	}
	/*
	for (i=0;i<n;i++) 
		printf("%d ",ind[i]);
	printf("\n");
	for (i=0;i<n;i++)
		printf("%d ",ord[i]);
	printf("\n");
	
	mergesort(ind,ord,c,d,0,n-1);
	/*
	for (i=0;i<n;i++) 
		printf("%d ",ind[i]);
	printf("\n");
	for (i=0;i<n;i++)
		printf("%d ",ord[i]);
	printf("\n");
	
	inplus=ord[0];
	//aflu cate culegeri am in plus pt dubluri
	for (i=1;i<n;i++) {
		if (ord[i]-ord[i-1]-1>0)
			inplus+=ord[i]-ord[i-1]-1;	
	}
	
	for (i=0;i<n;i++) {
	if (ord[i]!=-1 && acc>0) {
		if (i==0) {
			gt+=g[ind[i]].greutate;
			acc--;
			}
		else
			if (ord[i]==ord[i-1] ) {
				if (inplus>0)
					{
					gt+=g[ind[i]].greutate;
					inplus--;
					acc--;
					}
				}
			else
				{
				gt+=g[ind[i]].greutate;
				acc--;
				}
		}
	}
	*/
	
	for (i=0;i<n;i++)
		{
		if (g[i].inaltime<=h && acc>0)
			{
			gt+=g[i].greutate;
			acc--;
			}
		}
	
	fprintf(out,"%d\n",gt);		
	
return 0;
}