Cod sursa(job #435110)

Utilizator baktakNicoleta Iordachi baktak Data 6 aprilie 2010 22:06:00
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.07 kb
//#include<iostream>
//#include<fstream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

/******************************************************************************
 *									      *
 *		sortare() - sorteaza elementele unui vector 		      *
 *									      *
 ******************************************************************************/

void sortare(int hight[], int weight[], int n){

	int i, j, aux;
	
	for(i = 0; i<=n; i ++)
		for(j = i+1; j<n; j ++)
		
			if(hight[i]<hight[j]){
			
				aux = hight[j];
				hight[j] = hight[i];
				hight[i] = aux;
				
				aux = weight[j];
				weight[j] = weight[i];
				weight[i] = aux;	
			}

}


/******************************************************************************
 *									      *
 *	minim() - determina elementul minim dintr-un vector		      *
 *									      *
 ******************************************************************************/

int minim(int v[], int n){

	int i;
	int min = v[0];
	
	for(i = 1; i<n; i++)
		if(min > v[i])
			min = v[i];
		
	return min;
}


/******************************************************************************
 *									      *
 *	index() - determinarea pozitiei unui element intr-un vector	      *
 *									      *
 ******************************************************************************/

int index(int x, int v[], int n){

	int i;
	
	for(i = 0; i<n; i++)
		if(x == v[i])
			return i;
		
	return -1;
}


/******************************************************************************
 *									      *
 *		suma() - determinarea sumei elementelor dintr-un vector	      *
 *									      *
 ******************************************************************************/

int suma(int v[], int n){

	int i, s = 0;
	
	for(i = 0; i<n; i++)
		s += v[i];
	
	return s;
}


int main(){

	int n;			// nr de gutui
	int h;			// inaltimea maxima 
	int prag;		// inaltimea cu care se inalta ramurile
	int pr = 0;		// inaltimea curenta cu care se inalta ramurile
	int *hight; 		// inaltimile la care se afla initial ramurile
	int *weight; 		// greutatea fiecarei gutui
	
	int *cules;		// greutatea fiecarei gutui culese	
	int k = 0;		// lungimea vectorului cules[]
		
	int i;		// variabile auxiliare

	FILE *f, *g;
	f = fopen("gutui.in","r");
	g = fopen ("gutui.out","w");
	
	/* citire date de intrare */
	fscanf(f,"%d %d %d", &n, &h, &prag);

	hight = (int*)malloc(n*sizeof(int));
	weight = (int*)malloc(n*sizeof(int));

	for(i = 0; i<n; i++)
		fscanf(f, "%d %d", &hight[i], &weight[i]);
		
	sortare(hight, weight, n);
	
	cules = (int*)malloc(n*sizeof(int));
	
	for(i = 0; i<n; i ++)
		/* verificare daca Gigel poate ajunge la ramuri */
		if(hight[i]+pr <= h && pr <= h){

			cules[k++] = weight[i];
			/* cresterea inaltimii cu care se ridica ramurile */
			pr +=prag;

		}
		else{
			/* verificare daca nu a fost aleasa o greutate mai
			 * usoara decat cea curenta 			 */
			if(minim(cules,k) < weight[i]){
				cules[index(minim(cules,k),cules,n)] = weight[i];

			}
		}
		
	fprintf(g,"%d\n", suma(cules,k));	
	
	/* eliberare memorie */
	free(hight);
	free(weight);
	free(cules);
	
	fclose(f);
	fclose(g);
	return 0;
}