Cod sursa(job #441407)

Utilizator didi23Tiriplica Diana didi23 Data 12 aprilie 2010 21:54:19
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 2.69 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	unsigned int height;
	unsigned int weight;
	} gut;

void print (gut *g,unsigned int n)
{
	int i;
	for (i=0; i<n; i++)
		fprintf (stdout, "%d-------%d\n", g[i].height, g[i].weight);
	fprintf (stdout, "\n");
}

void print_heap (unsigned int *heap, unsigned int size)
{
	int i;
	for (i=0; i<size; i++)
		fprintf (stdout, "%d ", heap[i]);
	fprintf (stdout, "\n");
}
int cmp (const void *a, const void *b)
{
	return (*(gut*)a).height - (*(gut*)b).height;
}

void swap ( int* a , int* b )
{
	int aux;
	aux = *a;
	*a = *b;
	*b = aux;
}

unsigned int left (unsigned int i)
{
	return i*2+1;
}

unsigned int right (unsigned int i)
{
	return i*2 + 2;
}

unsigned int parent (unsigned int i)
{
	return (i-1)/2;
}

void up (unsigned int *heap, unsigned int poz)
{
	if (parent(poz) < 0 || poz == 0)
		return;
	if (heap[parent(poz)] < heap[poz])
	{
		swap (&heap[parent(poz)], &heap[poz]);
		poz = parent(poz);
		up (heap, poz);
	}
}

void heap_put (unsigned int *heap, unsigned int cost, unsigned int size)
{
	heap[size] = cost;
	up (heap, size);	
}

void down (unsigned int *heap, unsigned int poz, unsigned int size)
{
	unsigned int crt;
	
	if ( (left(poz) < size ) && ( heap[left(poz)] > heap[poz] ) )
		crt = left(poz);
	else
		crt = poz;

	if  ( (right(poz) < size ) && ( heap[right(poz)] > heap[crt] ) )
		crt = right(poz);	

	if ( crt != poz ) 
	{
		swap ( &heap[crt] , &heap[poz] );
		down ( heap , crt , size );
	}
}

unsigned int heap_get (unsigned int *heap, unsigned int size)
{
	unsigned int toret = heap[0];
	heap[0] = heap[size-1];
	down (heap, 0, size - 1);
	return toret;
}	

int main()
{
	FILE *fin, *fout;
	unsigned int n, u, h, i , max, niv, size, cnt;
	gut *gutui;
	unsigned int *heap;
	
	fin = fopen ("gutui.in", "r");
	fout = fopen ("gutui.out", "w");
	
	fscanf (fin, "%d %d %d\n", &n, &h, &u);
	if (n<1 || n>100000)
		return 1;
	gutui = (gut*)malloc(n*sizeof(gut));
	heap = (unsigned int*)calloc(n, sizeof(unsigned int));
	
	for (i=0; i<n; i++)
		fscanf (fin, "%d %d\n", &(gutui[i].height), &(gutui[i].weight));
		
	//print (gutui, n);
	qsort (gutui, n, sizeof(gut), cmp);
	print (gutui, n);
	
	max = 0;
	niv = gutui[0].height / u;
	cnt = gutui[0].height;
	i = 0;
	size = 0;
	while (i<n)
	{
	/*
		if (i == n)
		{
			max = max + heap_get(heap, size);
			break;
		}*/
		fprintf (stdout, "Pasul %d:\t", i);
		print_heap (heap, n);
		if (gutui[i].height / u == niv )
		{
			heap_put (heap, gutui[i].weight, size);
			size++;
			i++;
			continue;
		}
		max = max + heap_get(heap, size);
		cnt = cnt + u;
		size--;
		niv++;
	}
	printf ("%d\n", cnt);
	for (i=cnt; i<=h; i+=u)
		max = max + heap_get(heap, size);
	fprintf (fout, "%d\n", max);
	
	fclose (fin);
	fclose (fout);
	return 0;
}