Cod sursa(job #463392)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 17:00:00
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.84 kb
#include <stdio.h>
#include <stdlib.h>

int N;
unsigned int H, U;

typedef struct s {
	unsigned int h, m;
	} gutuie;

struct HeapStruct {
    int Capacity;
    int Size;
    gutuie* Elem;
};

typedef struct HeapStruct *Heap;

//definirea criteriului utilizat pentru sortarea gutuilor (descrescator dupa inaltime)
int compare (const void * a, const void * b) {
  	return ( ((*(gutuie*)b).h)/U - ((*(gutuie*)a).h)/U );
}

//definirea unor functii aplicate heap-ului
Heap initialize(int N) {
    Heap H;
    H = malloc(sizeof ( struct HeapStruct));
    H->Elem = malloc((N + 1) * sizeof (gutuie));
    H->Capacity = N;
    H->Size = 0;
    (H->Elem[0]).m = 32767;
    return H;
}

void insert(gutuie X, Heap H) {
    int i;
    for (i = ++H->Size; (H->Elem[ i / 2 ]).m < X.m; i /= 2)
        H->Elem[ i ] = H->Elem[ i / 2 ];
    H->Elem[ i ] = X;
}

gutuie findMax(Heap H) {
	return H->Elem[ 1 ];
}

gutuie deleteMax(Heap H) {
    int i, Child;
    gutuie MaxElement, LastElement;
	MaxElement = H->Elem[ 1 ];
	LastElement = H->Elem[ H->Size-- ];
	for (i = 1; i * 2 <= H->Size; i = Child) {
		Child = i * 2;
		if (Child != H->Size && (H->Elem[ Child + 1 ]).m > (H->Elem[ Child ]).m)
			Child++;
		if (LastElement.m < (H->Elem[ Child ]).m)
			H->Elem[ i ] = H->Elem[ Child ];
        else
			break;
	}
	H->Elem[ i ] = LastElement;
	return MaxElement;
}

int isEmpty(Heap H) {
    return H->Size == 0;
}

int max(int a, int b) {
	if(a > b)
		return a;
	return b;
}

int main() {
	FILE *fin = fopen("gutui.in","r");
	FILE *fout = fopen("gutui.out","w");
	
	//citirea datelor
	fscanf(fin,"%d%u%u",&N,&H,&U);
	gutuie* gutui = (gutuie*) malloc(N*sizeof(gutuie));
	int i;
	for(i = 0; i < N; i++) 
		fscanf(fin,"%u%u",&gutui[i].h,&gutui[i].m);
	unsigned int quantity = 0;
	
	//daca U = 0 problema este banala - se culeg toate gutuile
	if(U == 0) { 
		for(i = 0; i < N; i++)
			quantity += gutui[i].m;
		fprintf(fout,"%u\n",quantity);
		return 0;
	}
	
	//sortarea gutuilor, descrescator, dupa inaltime	
	qsort (gutui, N, sizeof(gutuie), compare);
	
	//daca H nu se divide cu U, se determina inaltimea de start
	int dif = U - H % U;
	unsigned int top;
  	if (dif == U) 
  		dif = 0;
  	int offset = U-dif;
  	top = 0;
  	
	Heap heap = initialize(N);
	int n = N-1;
	
	while((!isEmpty(heap) || n >= 0) && top <= H) {
		//se culege elementul cu masa maxima, aflat in heap
		if(!isEmpty(heap)) {
			quantity += (deleteMax(heap)).m;
			//se incrementeaza inaltimea curenta
      		top += U;
		}
		else {
			//se incrementeaza inaltimea curenta
			if(offset) {
				top += U * max(1, (gutui[n].h - top + offset) / U) - offset;
				offset = 0;
			}
			else 
				top += U * max(1, (gutui[n].h - top) / U);	
		}
		//se insereaza in heap toate gutuile aflate sub inaltimea curenta
		while (n >= 0 && gutui[n].h <= top) {
      		insert(gutui[n],heap);
      		n--;
    	}
	}
	
	fprintf(fout,"%u\n",quantity);
	fclose(fout);
	return 0;
}