Cod sursa(job #432907)

Utilizator giacolettoSir Cupcea giacoletto Data 2 aprilie 2010 22:42:36
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.69 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;	

	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(2*sizeof(long int));				//aloc memorie pentru prima linie	
	
		while ( ( fscanf(in, "%li %li", &linie[linie_curenta][0], &linie[linie_curenta][1] )  ) != EOF ) {		//citesc linie cu linie
			linie_curenta++;							//trec la linia urmatoare
			linie[linie_curenta] = (long int*)malloc(2*sizeof(long int));			//aloc memorie pentru linia urmatoare						
		}
			
	}

	fclose(in);
	return linie;
}

void afisare(unsigned 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);
}

int min (int a, int b) {
	return a<b ? a:b;
}



void swap(long int *x,long int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
 
void quicksort_array(long int list[],long int m,long int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = (m+n)/2;
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
      // swap two elements
      swap(&list[m],&list[j]);
      // recursively sort the lesser list
      quicksort_array(list,m,j-1);
      quicksort_array(list,j+1,n);
   }
}


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]);
	}
      }
      // swap two elements
      swap(&list[m][0],&list[j][0]);
      swap(&list[m][1],&list[j][1]);
      // recursively sort the lesser list
      quicksort(list,m,j-1);
      quicksort(list,j+1,n);
   }
}

void printlist(long int **list,long int n)
{
   long int i,j;
   for(i=0;i<n;i++) {
	for(j=0;j<2;j++)
      		printf("%li ",list[i][j]);
	printf("\n");
   }

}

int main() {		
	long int **mat;		
	long int i,j,pas_curent = 0;
	unsigned long int greutate_maxima = 0;
	long int v[N];			//vector de solutii partiale, in care memoram greutatile gutuilor, in ordine crescatoare	
	v[0] = 0;
	
	mat = citire ();		//citim datele. mat[i][0] ->inaltimea. mat[i][1] -> greutatea
   	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 ) {
			//inserez si sortez
			
			v[pas_curent++] = mat[i][1] ;
			quicksort_array(v,0,pas_curent-1);
			
		} else {
			if ( mat[i][1] >= v[0] ) {
				
				//scot primul element
				//inserez si sortez

				v[0] = mat[i][1];
				quicksort_array(v,0,pas_curent-1);
			}
		}

	}	
	

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

	afisare(greutate_maxima);
	return 0;
}