Cod sursa(job #440229)

Utilizator DarkHunterjCont cu nume gresit sau fals DarkHunterj Data 11 aprilie 2010 23:03:18
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.71 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct gutui
{
	int size;
	int weight;
}Gutue;

typedef struct wei
{
	int weight;
	struct wei * next;
	struct wei * prev;
}Weights,*AWeights;

AWeights makeNode(int x)
{
	AWeights aux=(AWeights) malloc(sizeof(Weights));
	aux->weight=x;
	aux->next=NULL;
	aux->prev=NULL;
	return aux;
}

int rem(int x, AWeights * lista)
{
	AWeights L = *lista;
	int aux;
	if(L==NULL)
		return 0;
	if(L->weight<x)
	{
		L->next->prev=NULL;
		(*lista)=L->next;
		aux=L->weight; 
		free(L);
		return aux; 
	}
	while(L!=NULL && L->weight>=x)
	{
		L=L->next;
	}
	if(L==NULL)
		return 0;
	else
	{
		L->prev->next=L->next;
		L->next->prev=L->prev;
		aux=L->weight;
		free(L);
		return aux;
	}
}

void insert(int x, AWeights * lista)
{
	AWeights L = *lista;
	AWeights aux = makeNode(x);
	if((*lista) == NULL)
	{
		(*lista)=aux;
		return;
	}
	if(L->weight<x)
	{
		L->prev=aux;
		aux->next=L;
		*lista=aux;
		return;
	}
	while(L->next!=NULL && L->next->weight>=x)
	{
		L=L->next;
	}
	if(L->next==NULL)
	{
		aux->prev=L;
		L->next=aux;
	}
	else
	{
		L=L->next;
		L->prev->next=aux;
		aux->prev=L->prev;
		aux->next=L;
		L->prev=aux;
	}
}

int rule(const void * a, const void *b)
{
	Gutue * A = (Gutue *) a;
	Gutue * B = (Gutue *) b;
	if(A->size > B->size)
		return -1;
	else if(A->size < B->size)
		return 1;
	else
		return B->weight-A->weight;
}

int main(int argc, char **argv)
{
	int maxsize, dif, removed, aux, step, n, i, total=0;
	int rest=0;
	AWeights lista=NULL;
	FILE * in = fopen("gutui.in","rt");
	FILE * out = fopen("gutui.out","wt");
	
	//Read data
	fscanf(in,"%i %i %i",&n,&maxsize,&step);
	Gutue *gut = (Gutue *) malloc(sizeof(Gutue) * n);
	maxsize ++;
	dif=maxsize%step;
	maxsize/=step;
	for(i=0;i<n;i++)
	{
		fscanf(in,"%i %i",&(gut[i].size),&(gut[i].weight));
		gut[i].size-=dif;
		gut[i].size/=step;
	}
	//Read data
	
	qsort(gut,n,sizeof(Gutue),rule);
	
	/*for(i=0;i<n;i++)
	{
		printf("%i %i\n",gut[i].size,gut[i].weight);
	}*/
	
	for(i=0;i<n;i++)
	{//eliminates "gutuis" that can't be reached
		if(gut[i].size<=maxsize)
			break;
	}
	
	for(;i<n;i++)
	{
		rest+=maxsize-gut[i].size;
		aux=gut[i].size;
		while(gut[i].size==aux && rest>0 && i<n)
		{
			total+=gut[i].weight;
			insert(gut[i].weight,&lista);
			i++;
			rest--;
		}
		if(rest==0)
		{	
			removed=1;
			while(gut[i].size==aux && i<n)
			{
				removed = rem(gut[i].weight, &lista);
				total-=removed;
				if(removed)
				{
					total+=gut[i].weight;
					insert(gut[i].weight,&lista);
				}
				else
					break;
				i++;
			}
			while(gut[i].size==aux && i<n)
				i++;
		}
		i--;
		maxsize=aux;
	}
	fprintf(out,"%i\n",total);
	
	/*while(lista!=NULL)
	{
		printf("%i\n",lista->weight);
		lista=lista->next;
	}
	
	scanf("%i",&i);*/
		
	fclose(in);
	fclose(out);
	return 0;
}