Cod sursa(job #435985)

Utilizator kp_itchyAlexandra kp_itchy Data 7 aprilie 2010 23:56:57
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.6 kb
#include<stdio.h>
#include<malloc.h>
int *c,*d;

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;
}

void swap2(int *a, int *b) {
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

//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];
		}
	}
	
	
void qsort2(int *ind, int *ord,int m, int n) {	
	int key,i,j,k;
	if (m<n)
		{
			k=choose_pivot(m,n);
			swap2(&ind[m],&ind[k]);
			swap2(&ord[m],&ord[k]);
			key=ord[m];
			i=m+1;
			j=n;
			while (i<=j)
				{
				while ((i<=n)&&(ord[i]<=key))
					i++;
				while ((j>=m) &&(ord[j]>key))
					j--;
				if (i<j) {
					swap2(&ind[i],&ind[j]);
					swap2(&ord[i],&ord[j]);
					}
				}
			swap2(&ind[m],&ind[j]);
			swap2(&ord[m],&ord[j]);
			qsort2(ind,ord,m,j-1);
			qsort2(ind,ord,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");
	
	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 m=-1,hmax=0,hmin=g[0].inaltime,aux,p;
	for (i=0;i<n;i++) {
		if (g[i].inaltime>hmax) hmax=g[i].inaltime;
		if (g[i].inaltime<hmin) hmin=g[i].inaltime;
	}
	//printf("max=%d\nmin=%d\n",max,min);	
	//max=(h-max)/u;
	//for (i=0;i<n;i++) ordine_cules[i]=0;
	int acc,inplus;
	acc=(h-hmin)/u+1;
	inplus=(h-hmax)/u;
	
	for (i=0;i<n;i++) {
		ind[i]=i;
		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");
	*/
	//qsort2(ind,ord,0,n-1);
	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");
	*/
	printf("acc=%d\n",acc);
	for (i=0;i<n;i++) {
		if (i==0 && acc>0) {
			gt+=g[ind[i]].greutate;
			acc--;
			}
		else
			if (ord[i]==ord[i-1]) {
				if (inplus>0 && acc>0)
					{
					gt+=g[ind[i]].greutate;
					inplus--;
					acc--;
					}
				}
			else
				{
				gt+=g[ind[i]].greutate;
				acc--;
				}
		}
		
	
	
	/*
	for (i=0;i<n;i++) {
		p=(h-g[i].inaltime)/u-max;
		if (ordine_cules[p]==0) ordine_cules[p]=i+1;
		else
			{
			aux=p+1;
			while (ordine_cules[aux]!=0) aux++;
			ordine_cules[aux]=i+1;	
			if (m<aux) m=aux;
			}
	}
	printf("nr.el=%d\n",aux+1);
	for (i=0;i<n;i++)
		printf("%d ",ordine_cules[i]);
	printf("\n");
	
	for (i=0;i<(h-min)/u+1;i++)
		gt+=g[ordine_cules[i]-1].greutate;
	*/	
	/*	
		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;
}