Cod sursa(job #435673)

Utilizator alexandra.savaAlexandra Sava alexandra.sava Data 7 aprilie 2010 19:10:28
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 3.43 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 struct gut{
	int h,w;
}Gutuie;


typedef struct hep{
	int val,poz;
}Heap;


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

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

	i = *size -1;
	while(i >0 && w > (*hp)[PARENT(i)].val){
		(*hp)[i].val =(*hp)[PARENT(i)].val;
		i = PARENT(i);
	}
	//printf("i %d este di w este %d\n",i,w);
	(*hp)[i].val = w;

}




int max( Heap **hp,int *size )
{
	int max, i,aux,np;
	if(*size == 0)
		return 0;
	
	max = (*hp)[0].val;
	//printf("size %d \n",*size);

	(*hp)[0].val = (*hp)[(*size) -1].val;
	aux = (*hp)[(*size) -1].val;
	(*hp)[(*size) -1].val = 0;
//	printf("au este %d \n",aux);	
	*size = *size - 1;

//	printf("inainte\n");
//	for(i = 0; i< *size; i++)
//		printf("%d ", (*hp)[i].val);
//	printf("\n");
	i = 0;
	while(i < *size && ((*hp)[CHILDONE(i)].val > aux || (*hp)[CHILDTWO(i)].val > aux) ){
	
		np = MAX( (*hp)[CHILDONE(i)].val,(*hp)[CHILDTWO(i)].val);
		
		if (np == (*hp)[CHILDONE(i)].val)
			np = CHILDONE(i);
		else
			np = CHILDTWO(i);
		//printf("np este %d ",np);	
		(*hp)[i].val = (*hp)[np].val; 

		i = np;
	}
//	printf("i este %d\n",i);	
	(*hp)[i].val = aux;
//	printf("dupa\n");
//	for(i = 0; i< *size; i++)
//		printf("%d ", (*hp)[i].val);
//	printf("\n");
		
	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;
		} 
			
	}
	/*
	for(i = 0; i < *n;i++){
		printf("gutuia %d are h de %d i cantareste %d \n",i,(*g)[i].h,(*g)[i].w);
	}
	*/	


}
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);
//		printf("intervalul la h %d este %d si ante este %d\n ",g[i].h,in,ante);
		if(ante == in){
			inserare(&hp,g[i].w,i,&sizeh);
			i++;
			if (i == n){
					i = m - in;
					//printf("m este %d \n",m);
					while(i > 0){
						mx =  max(&hp,&sizeh);
					//	printf("ultim mx este %d si i este %d intervalul este %d\n",mx,i,in);
						nr = nr +mx;
						if(mx == 0)
							break;
						i --;
					}
					break;
				}
					
			continue;
		
		
		}
		mx =  max(&hp,&sizeh);
	//	printf("max este %d si i este %d intervalul este %d\n",mx,i,in);
		nr = nr + mx;
		ante ++;
	}
		
		
	return nr;

}


int compare(const void *a, const void *b)
{
	Gutuie *m,*n;
	m = (Gutuie*)a;
	n = (Gutuie*)b;

	return  (m->h - n->h);            
}


int main()
{	int n,H,U,nr;
	FILE *f;
	Gutuie *g;
	read(&g,&n,&H,&U,"gutui.in");
	qsort(g,n,sizeof(Gutuie),compare);

/*

	for(i = 0 ; i< n; i++)
		printf(" gutuia %d are h %d si w %d\n",i,g[i].h,g[i].w);

*/
	nr = nrGutui(g,n,H,U);
	f = fopen("gutui.out","w");
	fprintf(f,"%d",nr);
	fclose(f);

	return 0;

}