Cod sursa(job #436131)

Utilizator alexandra.savaAlexandra Sava alexandra.sava Data 8 aprilie 2010 03:41:52
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.31 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>


#define MAX(a,b)( (a-b <=0) ? ( b):(a) )
#define PARENT(i) ((i % 2 == 0 )?(i/2 -1) : (i/2))
#define CHILDONE(i) (2*i + 1)
#define CHILDTWO(i) (2*i + 2)

typedef int Heap;

typedef struct gut{
	int h,w;
}Gutuie;



void inserare(Heap **hp, int w, int in, int *size)
{	int i = 0;	

	(*hp)[*size] = w;
	*size = *size + 1;
	
	if(*size == 1)
		return;

	i = *size -1;
	
	while(i >0 && w > (*hp)[PARENT(i)]){
		
		(*hp)[i] =(*hp)[PARENT(i)];
		i = PARENT(i);
	}
	
	(*hp)[i] = w;

}


int max( Heap **hp,int *size )
{
	int max, i,aux,np;
	
	if(*size == 0)
		return 0;
	
	max = (*hp)[0];

	(*hp)[0] = (*hp)[(*size) -1];
	aux = (*hp)[(*size) -1];
	(*hp)[(*size) -1] = 0;
	
	*size = *size - 1;
	
	if(*size == 1)
		return max;
	i = 0;
	while(i < *size && ((*hp)[CHILDONE(i)] > aux || (*hp)[CHILDTWO(i)] > aux) ){
		
		np = MAX( (*hp)[CHILDONE(i)],(*hp)[CHILDTWO(i)]);
		
		if (np == (*hp)[CHILDONE(i)])
			np = CHILDONE(i);
		else
			np = CHILDTWO(i);
		
		(*hp)[i] = (*hp)[np]; 

		i = np;
		
		if(CHILDONE(i) >= *size)
			break;
	}
	
	(*hp)[i] = aux;
		
	return max;
	
}


void read(Gutuie **g, int *n, int *H, int *U, char *file)
{
	FILE *f;
	int i = 0,hh,gg;

	f = fopen(file, "r");

	fscanf(f,"%d %d %d ",n,H,U);
	
	(*g) = (Gutuie *)malloc((*n)*sizeof(Gutuie));
	
	*n = 0;
	
	while(fscanf(f,"%d %d ",&hh,&gg) > 0 ){
		if(hh <= *H){
			(*g)[i].h = hh;
			(*g)[i].w = gg;
			i++;
			(*n) = (*n) + 1;
		} 
			
	}

}

int interval(int U, int H, int n){
	
	int r;

	r = H % U;

	if(n <= r)
		return 0;
	
	if(r == 0){
		if(n % U == 0)
			return (n/U -1);
		else
			return n/U;
	}

	n = n - r;
	

	if(n % U == 0)
		return n/U;
	else
		return n/U + 1;
	
}


int nrGutui(Gutuie *g, int n, int H, int U)
{
	int i,m,nr = 0,ante,in,sizeh,mx;
	Heap *hp;
	
	hp = (Heap*)malloc(n * sizeof(Heap));

	if(H % U == 0)
		m = H / U ;
	else
		m = H / U + 1;
	
	i = 0;
	
	ante = interval(U,H,g[0].h);
	sizeh = 0;
	
	while(i < n){
		
		in = interval(U,H,g[i].h);
		if(ante == in){
			inserare(&hp,g[i].w,i,&sizeh);
			i++;
			if (i == n){
					i = m - in;
					while(i > 0){
						mx =  max(&hp,&sizeh);
						nr = nr + mx;
						if(mx == 0)
							break;
						i --;
					}
					break;
				}
					
			continue;
		
		
		}
	
		nr = nr + max(&hp,&sizeh);
		ante ++;
	}
		
		
	return nr;

}

int compare(int a, int b)
{
	return a-b;           
}

void merge(Gutuie **g, int p, int q)
{
	int m,i,j,t=0;
	Gutuie *aux;
	aux = (Gutuie*)malloc((q-p+1)*sizeof(Gutuie));
	m= (p + q )/ 2;
	
	i = p;
	j = m + 1;
	while(i <=m && j <=q){
		if(compare((*g)[i].h,(*g)[j].h) < 0 ){
			aux[t] =(*g)[i];
			i++;
		}
		else{
			aux[t] = (*g)[j];
			j++;
		}
		t ++;
	}
	while(i<=m){
		aux[t]=(*g)[i];
		i++;
		t++;
	}
	while(j<=q){
		aux[t]=(*g)[j];
		j++;
		t++;
	}
	m = p;
	for(i = 0; i < t; i++){
		(*g)[m] = aux[i];
		m ++;
	}
	free(aux);

}




void MergeSort(Gutuie **g, int p, int q)
{
	int m;
	Gutuie gt;
	if(p > q)
		return;
	if(q - p == 0){
		return;
	}
	if(q - p == 1){
		if(compare((*g)[p].h,(*g)[p+1].h)>0 ){
			gt = (*g)[p];
		 	(*g)[p]=(*g)[p+1];
			(*g)[p+1] = gt;
			return;
			}
	}
	m = (p + q) / 2;
	MergeSort(g,p,m);
	MergeSort(g,m+1,q);
	merge(g,p,q);
}
	
int main()
{	int n,H,U,nr;
	FILE *f;
	Gutuie *g;
	read(&g,&n,&H,&U,"gutui.in");
	MergeSort(&g,0,n-1);
	nr = nrGutui(g,n,H,U);
	f = fopen("gutui.out","w");
	fprintf(f,"%d",nr);
	fclose(f);

	return 0;

}