Cod sursa(job #436631)

Utilizator alexandra.savaAlexandra Sava alexandra.sava Data 8 aprilie 2010 18:30:17
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.7 kb
#include<stdio.h>
#include<stdlib.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 *size)
{	
	int i = 0;	

	(*hp)[*size] = w;
	*size = *size + 1;
	
	//daca dupa o inserare, numarul elementelor din heap == 1, este redundanta o refacere a heapului	
	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 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 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;
	
}
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,&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(const void *a, const void *b)
{
	Gutuie *m,*n;
	m = (Gutuie*)a;
	n = (Gutuie*)b;

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



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 main()
{	int n,H,U,nr;
	FILE *f;
	Gutuie *g;
	
	read(&g,&n,&H,&U,"gutui.in");
	
	qsort(g,n,sizeof(Gutuie),compare);
	
	nr = nrGutui(g,n,H,U);
	
	f = fopen("gutui.out","w");
	
	fprintf(f,"%d",nr);
	
	fclose(f);

	return 0;

}