Cod sursa(job #437741)

Utilizator mirunici2389Miruna Popescu mirunici2389 Data 10 aprilie 2010 00:55:16
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.59 kb
#include<stdio.h>
#include<stdlib.h>

//structura gutuie
typedef struct gut
{
	int nivel;
	int greutate;
	int inaltime;
}gutui;

//fct de comparare pt qsort - sorteaza gutui in fct de nivel si greutate
int comparator(const void * a,const void *b)
{
	gutui *aa=(gutui *)a; 
	gutui *bb=(gutui *)b; 
	if ((*aa).nivel != (*bb).nivel) return (*aa).nivel-(*bb).nivel;
	return (*bb).greutate-(*aa).greutate;
}

//fct de comparare pt qsort - sorteaza gutui in fct de inaltime
int comparator2(const void * a,const void *b)
{
	gutui *aa=(gutui *)a; 
	gutui *bb=(gutui *)b; 
	return (*bb).inaltime-(*aa).inaltime;
}

//fct intoarce pozitia pe care se gaseste minimul dintr-un vector
int poz_minim(int vector[], int n)
{
	int i;
	int poz = 0;
	int min = vector[0];
	for (i=0;i<n;i++)
	{
		if (vector[i] < min)
		{
			min = vector[i];
			poz = i;
		}
	}
	return poz;
}

int main()
{
	FILE *f=NULL,*g=NULL;
	int N,H,U,nr_niv;
	int i,j,n,niv,pozitie,k;
	int greutate_culeasa=0;
	gutui *mat, *mat2;
	
	//citesc datele de intrare si calculez nivelele pe care sunt asezate gutuile
	f=fopen("gutui.in","rt");
	g=fopen("gutui.out","wt");	
	fscanf (f,"%i%i%i",&N,&H,&U);
	nr_niv=H/U;
	if(H%U != 0) nr_niv++;
	mat = (gutui*)malloc(N*sizeof(gutui));
	for(i=0;i<N;i++)
	{
		fscanf(f,"%i%i",&(mat[i].inaltime),&(mat[i].greutate));
		if (mat[i].inaltime > H ) mat[i].nivel = 0;
		else mat[i].nivel = ((H-mat[i].inaltime) / U )+1;
		
	}
	
	//sortez gutuile in functie de nivel si greutate	
	//qsort(mat, N, sizeof(gutui), comparator);	
			
	//creez un nou vector de gutui doar cu cele la care gigel poate ajunge
	//de pe un nivel i gigel poate culege maxim i gutui, 
	//le vom pastra pe primele cele mai grele de pe acel nivel
	n=0;
	i=0;
	mat2 = (gutui*)malloc(N*sizeof(gutui));
	
	
	/*while(i<N)
	{
		niv=mat[i].nivel;
		j=0;
		while ((niv == mat[i].nivel) && (i<N) && (j<niv))
		{
			mat2[n]=mat[i];
			n++;
			i++;
			j++;
		}
		while ((mat[i].nivel == niv) && (i<N)) i++;
	}
	N=n;*/	
	
	//sortez dupa inaltime
	qsort(mat, N, sizeof(gutui), comparator2);
	
	//creez un vector cu greutatile gutuilor pe care le culeg
	
	int greutati[N];
	i=0;
	niv=0;
	for(j=0;j<N;j++)
	{
		if (mat[j].nivel>niv) 
		{
			greutati[i]=mat[j].greutate;
			i++;
			niv++;
		}
		else
		{
			pozitie=poz_minim(greutati,i);
			if(mat[j].greutate > greutati[pozitie]) greutati[pozitie] = mat[j].greutate;
		}
	}
	n=i;
	
	//scriu datele de iesire
	for (i=0;i<n;i++)
		greutate_culeasa += greutati[i];
	fprintf(g,"%i",greutate_culeasa);
	
	fclose(f);
	fclose(g);
	return 0;
}