Cod sursa(job #463283)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 22:05:35
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.2 kb
#include <stdlib.h>
#include <stdio.h>
unsigned long hmax, inc, max;
int nr;
typedef struct Gutui
{
	unsigned long h, w, k;
} *gutui;

void ord(gutui *pom)
{
	int i,j;
	gutui gut;
	for (i = 0; i < nr; i++)
		for (j = 0; j < nr; j++)
		{
			if (pom[i]->k < pom[j]->k) 
			{
				gut = pom[i];
				pom[i] = pom[j];
				pom[j] = gut;
			}
			else 
			if (pom[i]->k == pom[j]->k) 
			{
				if (pom[i]->w > pom[j]->w)
				{
				gut = pom[i];
				pom[i] = pom[j];
				pom[j] = gut;
				}
			}
		}
}

void scoateMin(int *vector, int m)
{
	int i;
	for (i = 0; i < m - 1 ; i++)
		vector[i] = vector[i + 1];
}

int *pune(gutui *pom, int *vector, int val, int m)
{
	
	int i = 0;
	int *aux;
	aux = (int*) calloc (max, sizeof(int));
	if (m == 0)
		aux[0] = val;
	else
	{
		while (pom[vector[i]]->w < pom[val]->w && i < m)
		{
			aux[i] = vector[i];
			i++;
		}
		aux[i] = val;
		while ( i < m)
		{
			aux[i + 1] = vector[i];
			i++;
		}
	}
	
	return aux;
}

unsigned long culege(gutui *pom)
{
	unsigned int l = 0;
	unsigned long rez = 0;
	unsigned int i, m = 0;
	int *vector;
	
	vector = (int*) calloc(max, sizeof(int));
	for ( i = 0; i < nr; i++)
	{
		if (pom[i]->k > l)
		{
			
			vector = pune(pom, vector, i, m);
		
			l++;
			m++;
		
		}
		else 
		if (pom[i]->k == l) // daca poate, sa schimbe gutuiul cules cu altul 
		{
			if (pom[vector[0]]->w < pom[i]->w)
			{
				scoateMin(vector, m);
				vector = pune(pom, vector, i, m - 1);
			}
		}
	}

	for (i = 0; i < m; i++)
		
		{
			rez += pom[vector[i]]->w;
		}
free(vector);
return rez;
}

int main()
{
	FILE *f, *g;
	gutui *pom;
	unsigned long rez;
	int i;
		
	f = fopen("gutui.in", "r");
	g = fopen("gutui.out", "w");
	fscanf(f,"%d %lu %lu", &nr, &hmax, &inc);
	pom = (gutui*) malloc (nr * sizeof(gutui));
	for (i = 0; i < nr; i++)
	{
		pom[i] = (gutui) malloc (sizeof(struct Gutui));
		fscanf(f, "%lu %lu", &pom[i]->h, &pom[i]->w);
		if (pom[i]->h > hmax)
		{
			pom[i]->k = 0;
		}
		else 
		{
			pom[i]->k = (hmax - pom[i]->h) / inc + 1;
		}
	}	
	
	ord(pom);
	max = pom[nr-1]->k + 1;
	rez = culege(pom);
	fprintf(g,"%lu", rez);
		
fclose(f);
fclose(g);
return 0;
}