Cod sursa(job #463696)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 17 iunie 2010 11:58:48
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.42 kb
//Tigora Andrei 322CA
#include<stdio.h>
#include<stdlib.h>

typedef struct	{
		int w;
		int h;
		} gutuie;
typedef struct	{
		int max;
		int crt;
		int* w;
		} heap;

int compare(gutuie a,gutuie b){
	/*
	 *	Functie de comparatie intre 2 elemente de tip "gutuie".
	 *	Elementele sunt sortate crescator dupa h, iar in caz de
	 *	egalitate descrescator dupa w.
	*/
	if(a.h<b.h)
		return -1;
	if(a.h>b.h)
		return 1;
	if(a.w>b.w)
		return -1;
	if(a.w<b.w)
		return 1;
	return 0;
}


void merge_sort(gutuie *vect,int size){
	/*
	 *	MergeSort banal fara nimic deosebit... banal
	*/
	
	gutuie aux;
	
	if(size==1)	
		return;
	if(size==2){
		if(compare(vect[0],vect[1])>0){
			aux = vect[0];
			vect[0] = vect[1];
			vect[1] = aux;
		}
		return;
	}
	int middle = size/2,i,j,crt;
	gutuie *vect1 = malloc((middle)*sizeof(gutuie));
	gutuie *vect2 = malloc((size-middle)*sizeof(gutuie));
	for(i=0;i<middle;i++)
		vect1[i] = vect[i];
	for(i=middle;i<size;i++)
		vect2[i-middle] = vect[i];
	
	merge_sort(vect1,middle);
	merge_sort(vect2,size-middle);
	
	i = 0, j = 0, crt = 0;
	while(i<middle && j<size-middle)
		if(compare(vect1[i],vect2[j])<=0)
			vect[crt++] = vect1[i++];
		else
			vect[crt++] = vect2[j++];
	while(i<middle)
		vect[crt++] = vect1[i++];
	while(j<size-middle)
		vect[crt++] = vect2[j++];
	free(vect1);free(vect2);
}

void remove_first(heap *choice){
	/*
	 *	Functie de eliminare a varfului heapului... neinteresant
	 */
	choice->crt--;
	choice->w[0] = choice->w[choice->crt];
	int poz = 0;
	int aux;
	while(1){
		if(poz*2+2<choice->crt){	//are ambii fii
			if(choice->w[poz*2+1]<choice->w[poz]){//primul fiu mai mic decat curentul
				if(choice->w[poz*2+2]<choice->w[poz*2+1]){//al doilea mai mic decat primul
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+2];
					choice->w[poz*2+2] = aux;
					poz = poz*2+2;
				}
				else{//primul mai mic decat al doilea
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+1];
					choice->w[poz*2+1] = aux;
					poz = poz*2+1;
				}
			}
			else{//tatal mai mare ca primul fiu
				if(choice->w[poz*2+2]<choice->w[poz]){//al doilea fiu mai mic
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+2];
					choice->w[poz*2+2] = aux;
					poz = poz*2+2;
				}
				else//ambii fii mai mari
					break;
			}
		}
		else	//doar un fiu
			if(poz*2+1<choice->crt){
				if(choice->w[poz*2+1]<choice->w[poz]){//fiul este mai mic
					aux = choice->w[poz];
					choice->w[poz] = choice->w[poz*2+1];
					choice->w[poz*2+1] = aux;
					poz = poz*2+1;
				}
				else	//fiul este mai mare
					break;
			}
			else	//nu are fii
				break;
	}
}

void add(heap *choice,int val){
	/*
	 *	Functie de adaugare in heap... ca mai sus
	 */
	int poz = choice->crt;
	int aux;
	choice->crt++;
	choice->w[poz] = val;
	while(poz)
		if(choice->w[poz]<choice->w[(poz-1)/2]){
			aux = choice->w[poz];
			choice->w[poz] = choice->w[(poz-1)/2];
			choice->w[(poz-1)/2] = aux;
			poz = (poz-1)/2;
		}
		else
			break;	
}

int main(){
	int i,crt,n;
	gutuie *vect;
	int high_max,low;
	long long suma = 0;
	heap choice;
	FILE *in,*out;
	
	in = fopen("gutui.in","r");
	out = fopen("gutui.out","w");
	
	//	Citirea datelor de intrare
	fscanf(in,"%d%d%d",&n,&high_max,&low);
	vect = malloc(n*sizeof(gutuie));
	
	//	Se elimina gutuile care sunt mai sus decat high_max(H in enunt)
	crt = 0;
	for(i=0;i<n;i++){
		fscanf(in,"%d%d",&vect[crt].h,&vect[crt].w);
		if(vect[crt].h<=high_max){	//	gutuie accesibila
			crt++;
		}
	}
	n = crt;//	reactualizare n
	
	if(crt==0){//	daca nu exista gutui, rezolvarea se incheie aici
		free(vect);
		fclose(in);fclose(out);
		fprintf(out,"%lld",suma);
		return 0;
	}
	//	Inaltimea este inlocuita cu nivelul corespunzator
	for(i=0;i<n;i++)
		vect[i].h = ((high_max - vect[i].h) / low) + 1;
	//	Sorteaza corespunzator
	merge_sort(vect,n);
	//	Initializeaza minheapul
	if(vect[n-1].h > n){
		choice.w = malloc(n*sizeof(int));
		choice.max = n;
	}
	else{
		choice.w = malloc(vect[n-1].h*sizeof(int));
		choice.max = vect[n-1].h;
	}
	choice.crt=0;
	//	Adauga in minheap
	for(i=0;i<n;i++){
		if(vect[i].h>choice.crt)//mai sunt gutui accesibile pe nivelul curent
			add(&choice,vect[i].w);
		else if(vect[i].w > choice.w[0]){
			//	gutuia curenta reprezinta o alegerea mai buna decat 
			//	cea mai slaba alegere anterioara
			remove_first(&choice);
			add(&choice,vect[i].w);
		}
	}
	
	//	Calculul sumei
	for(i=0;i<choice.crt;i++)
		suma+=choice.w[i];
	fprintf(out,"%lld",suma);
	
	free(vect);free(choice.w);
	fclose(in);fclose(out);
	//	End
	return 0;
}