Cod sursa(job #432950)

Utilizator giacolettoSir Cupcea giacoletto Data 3 aprilie 2010 00:15:30
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.56 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_array(long int list[],long int m,long int n)
{
   long 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");
   }

}

/*
void insereaza_si_pastreaza_sortarea ( long int *v, long int inceput, long int sfarsit,long int val ) {
	long int k;
	long int pas_curent = sfarsit;
	k = (inceput + sfarsit)/2;
	if ( i < k ) 
		insereaza_si_pastreaza_sortarea (v,inceput,k,val);
	else 
		insereaza_si_pastreaza_sortarea (v,k,sfarsit,val);
}

*/


void insertion_sort(long int x[],long int length)
{
  long int key,i,j;
  for(j=0;j<length;j++)
  {
     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;
	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

//printlist(mat,N);
	for( i =N-1; i>=0; i--) {
		if ( ( (H - mat[i][0]) / U ) >= pas_curent ) {
			//inserez si sortez
//			printf("(H - mat[%li][0]) / U %li pas_curent %li, mat[%li][0]%li \n",i,(H - mat[i][0]) / U, pas_curent,i, mat[i][0]);	
			v[pas_curent++] = mat[i][1] ;
			insertion_sort(v,pas_curent-1);
			//pas_curent++;		
		//	quicksort_array(v,0,pas_curent-1);
			
		} else {
			if ( mat[i][1] > v[0] ) {
//				printf("mat[%li][1], %li \n",i,mat[i][1]);
				//scot primul element
				//inserez si sortez

				v[0] = mat[i][1];
				insertion_sort(v,pas_curent-1);
				//quicksort_array(v,0,pas_curent-1);
			}
		}
/*
for (  j = 0; j <= pas_curent-1; j++ )  {
	
	printf("%li ``",v[j]);
}
puts("\n");
*/
	}	
	

	for (  j = 0; j < pas_curent; j++ )  {
			greutate_maxima+=v[j];
	}	
//printf("gmax: %li\n",greutate_maxima);
	afisare(greutate_maxima);
	return 0;
}