Cod sursa(job #440529)

Utilizator catalin_olariOlari Catalin Georgel catalin_olari Data 12 aprilie 2010 06:35:36
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.36 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long int N; //numar gutui
long int H; //inaltimea maxima la care ajunge gigel
long int U; //inaltimea cu care se ridica gutuiele, dupa ce a cules o gutuie

long int** citire () {

	FILE *in;
	long int **linie;
	long int linie_curenta = 0, i;	

	if ( (in = fopen("gutui.in", "r") ) == NULL) {
	    printf("Nu am putut deschide fisierul de intrare.\n");
	    exit(1);
	} else {
		fscanf(in,"%li %li %li",&N,&H,&U);


		linie = (long int**)malloc( (N+1) * sizeof(long int*) );				//aloc memorie initial pentru toata structura
		linie[linie_curenta] = (long int*)malloc(3*sizeof(long int));				//aloc memorie pentru prima linie	

		for (i=0;i<N;i++) {
			fscanf(in, "%li %li", &linie[linie_curenta][0], &linie[linie_curenta][1] );	//citesc linie cu linie
			linie_curenta++;								//trec la linia urmatoare
			linie[linie_curenta] = (long int*)malloc(3*sizeof(long int));			//aloc memorie pentru linia urmatoare	
		}			
	}

	fclose(in);
	return linie;
}

void afisare(long int g) {
	FILE *out;
	
	if ( (out = fopen("gutui.out", "w") ) == NULL) { 
		printf("Nu am putut deschide fisierul de iesire.\n");
		exit(1);
	} else {	
		fprintf(out,"%li", g);
	}	
		
	fclose(out);
}



void swap(long int *x,long int *y) {
	long int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}


void quicksort(long int **list,long int m,long int n) {
	long int key,i,j,k;

	if( m < n) {
		k = (m+n)/2;			//alegem pivot
		swap(&list[m][0],&list[k][0]);
		swap(&list[m][1],&list[k][1]);
		key = list[m][0];
		i = m+1;
		j = n;

		while(i <= j) {
			 while((i <= n) && (list[i][0] <= key))
				i++;
			 while((j >= m) && (list[j][0] > key))
				j--;
			 if( i < j) {
				swap(&list[i][0],&list[j][0]);
				swap(&list[i][1],&list[j][1]);
			}
		}

		//schimba 2 elemente intre ele
		swap(&list[m][0],&list[j][0]);
		swap(&list[m][1],&list[j][1]);

		//sorteaza recursiv listele mai mici
		quicksort(list,m,j-1);
		quicksort(list,j+1,n);
	}
}


void insertion_sort(long int x[],long int length) {
	long int key,i,j;
	 
	j = length-1;	//stiu ca decat ultimul element nu este la locul lui
	key = x[j];
	i = j-1;

	while( x[i] > key && i >= 0 ) {
	     x[i+1] = x[i];
	     i--;
	}

	x[i+1]=key;

}

int main() {		
	long int **mat;		
	long int i,j,pas_curent = 0,eliminari = 0;
	long int greutate_maxima = 0;	
	mat = citire ();					//citim datele. mat[i][0] ->inaltimea. mat[i][1] -> greutatea

	long int v[N];						//vector de solutii partiale, in care memoram greutatile gutuilor, in ordine crescatoare	
	v[0] = 0;

	quicksort(mat,0,N-1);					//ordonam gutuile dupa inaltimea la care se afla initial

	for( i =N-1; i>=0; i--) {

		if ( ( (H - mat[i][0]) / U ) >= pas_curent - eliminari ) {	//daca Gigel nu trebuie sa renunte la niciun pas anterior ca sa ajunga sa culeaga gutuia curenta
			v[pas_curent++] = mat[i][1] ;				//adaug greutatea la sfarsitul vectorului				
			insertion_sort(v, pas_curent);  			//sortez			
		} else {
			if ( mat[i][1] > v[eliminari] ) {			//daca greutatea gutuii este mai mare decat cea mai mica greutate pe care am cules-o deja
				v[eliminari++] = 0;				//renunt la gutuia cu cea mai mica greutate si o inlocuiesc cu cea curenta	
				v[pas_curent++] = mat[i][1] ;			//adaug greutatea la sfarsitul vectorului				
				insertion_sort(v, pas_curent); 			//sortez
			}
		}
	}	
	

	for (  j = 0; j < pas_curent; j++ )  {
			greutate_maxima+=v[j];
	}	

	afisare(greutate_maxima);
	return 0;
}