Cod sursa(job #434766)

Utilizator alexandra.savaAlexandra Sava alexandra.sava Data 6 aprilie 2010 15:23:25
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 1.89 kb
#include<stdio.h>
#include<stdlib.h>

#define VAL(a,b) ((a) % (b) == 0 ? ((a)/(b) -1) : ((a)/(b)))

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



int max(Gutuie **v, int n )
{
	int i, max ,p;
	max = (*v)[0].w;
	p = 0;

	for(i = 1; i < n; i++){
		if((*v)[i].w > max){
			max = (*v)[i].w;
			p = i;
		}
	}
	if(max != 0){
		(*v)[p].w = 0;
	}
	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;

	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,j,m,nr = 0,p;
	int *v;
	if(H % U == 0)
		m = H / U ;
	else
		m = H / U + 1;
		
	v = (int*)calloc(m , sizeof(int));

if(H % U == 0){
	for(i = 0; i < n; i++){
		if((g[i].h) % U == 0 )
			j = (g[i].h) / U -1;

		else
			j = (g[i].h) / U ;
		v[j] = v[j] + 1;
	}
}
else{
	for(i = 0; i < n; i++){
		
		j = interval(U,H,g[i].h);
		v[j] = v[j] + 1;
	}



}
	
	i = interval(U,H,g[0].h);
	p = 0;
	for(; i < m; i++){
		if(v[i] != 0)
			p = p + v[i];
		nr = nr + max(&g,p);
	}
	

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;

}