Cod sursa(job #439461)

Utilizator mirunici2389Miruna Popescu mirunici2389 Data 11 aprilie 2010 16:22:18
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.37 kb
#include<stdio.h>
#include<stdlib.h>

//structura celula pt lista simplu inlantuita
typedef struct cel
{
	cel * next;
	int g;
}celula, *Acelula;

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

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

//fct insereaza o celula in lista pastrand ordinea crescatoare
void insereaza(Acelula q, Acelula *greutati)
{
	Acelula p = *greutati;
	//inseram q inaintea listei
	if (q->g <= p->g)
	{
		q->next = p;
		*greutati=q;
		return;
	}
	
	//inseram q dupa celula p
	while(p->next)
	{
		if ((q->g > p->g)&&(q->g <= (p->next)->g)) 
		{
			q->next = p->next;
			p->next=q;
			return;
		}
		else p=p->next;
	}
	
	//se analizeaza cazul cand inseram ultima celula
	p->next = q;
}

int main()
{
	FILE *f=NULL,*g=NULL;
	int N,H,U;
	int i,j,niv;
	int greutate_culeasa=0;
	gutui *mat;
	Acelula q, p, *greutati;
	
	//citesc datele de intrare si calculez nivelele pe care sunt asezate gutuile
	f=fopen("gutui.in","rt");	
	fscanf (f,"%i%i%i",&N,&H,&U);
	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 dupa inaltime
	qsort(mat, N, sizeof(gutui), comparator2);
	
	//creez o lista dublu inlantuita cu greutatile gutuilor pe care le culeg
	p = (celula*) malloc(sizeof(celula));
	p->next = NULL;
	p->g = mat[0].greutate;
	greutati = &p;
	
	niv=1;
	for(j=1;j<N;j++)
	{
		q=(celula*) malloc(sizeof(celula));
		q->next = NULL;
		q->g = mat[j].greutate;
		if (mat[j].nivel>niv) 
		{
			//inroduc gutuia in cele culese si incrementez nivelul
			insereaza(q,greutati);
			niv++;
		}
		else if(q->g > (*greutati)->g) 
		{
		/*	//eliberez valoarea minima
			//q=*greutati;
			greutati=&((*greutati)->next);
			//free(q);
			//introduc noua valoare
			insereaza(q,greutati);*/
		}
		
	}
	//scriu datele de iesire
	g=fopen("gutui.out","wt");
	while((*greutati))
	{
		//q=*greutati;
		greutate_culeasa += (*greutati)->g;
		greutati = &((*greutati)->next);
		//free(q);
	}
	fprintf(g,"%i",greutate_culeasa);
	fclose(f);
	fclose(g);
	return 0;
}