Cod sursa(job #434820)

Utilizator violeta.marinVioleta Marin violeta.marin Data 6 aprilie 2010 16:42:37
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.33 kb
#include <stdio.h>
#include <stdlib.h>


struct gut{
	unsigned int inalt;	
	unsigned int greu;
	unsigned int index;
	  };

int compare_in (const void * a, const void * b)
{
	if ((*(struct gut*)a).inalt == (*(struct gut*)b).inalt) 
		return -((*(struct gut*)a).greu - (*(struct gut*)b).greu); 
	return -((*(struct gut*)a).inalt - (*(struct gut*)b).inalt);
	 	
}


int compare_gr (const void * a, const void * b)
{
	if ((*(struct gut*)a).greu == (*(struct gut*)b).greu)
		return -((*(struct gut*)a).inalt - (*(struct gut*)b).inalt);
	return -((*(struct gut*)a).greu - (*(struct gut*)b).greu); 
}

int max_lost (struct gut *gutui_in, unsigned int pas, unsigned int *i, unsigned int n, unsigned int u, unsigned int h, unsigned char * cules){
	unsigned int gr = 0, j;
	
	for (j = *i; j < n; j++)
		{
		if ((gutui_in[j].inalt + pas * u < h)&&(cules[gutui_in[j].index] == 0)) 
			break;
		if ((gutui_in[j].greu > gr)&&(cules[gutui_in[j].index] == 0))
			gr = gutui_in[j].greu;
		cules[gutui_in[j].index] = 1;
		}
	 *i = j;
	return gr;	
}
	
int main(){
	int i, j;
	FILE *f = fopen("gutui.in","r");
	unsigned int n = 0,h = 0 ,u = 0, max = 0, gr;
	fscanf(f, "%d", &n);
	fscanf(f, "%d", &h);
	fscanf(f, "%d", &u);
	
	//struct gut *gutui = (struct gut *)malloc(n * sizeof(struct gut));
	unsigned char *cules = (unsigned char *)calloc(n, sizeof(unsigned char));
	

	struct gut *gutui_in = (struct gut *)malloc(n * sizeof(struct gut));
	struct gut *gutui_gr = (struct gut *)malloc(n * sizeof(struct gut));	

	for (i = 0; i < n; i++)
		{
		fscanf(f, "%u", &gutui_in[i].inalt);
		fscanf(f, "%u", &gutui_in[i].greu);
		gutui_gr[i].inalt = gutui_in[i].inalt;
		gutui_gr[i].greu = gutui_in[i].greu;
		gutui_in[i].index = i;	
		gutui_gr[i].index = i;
		}
	fclose(f);

	qsort(gutui_in, n, sizeof(struct gut), compare_in);
	qsort(gutui_gr, n, sizeof(struct gut), compare_gr); 

	/*for (i = 0; i < n; i++)
		{
		printf("%u ", gutui_in[i].index);
		printf("%u ", gutui_in[i].inalt);
		printf("%u\n", gutui_in[i].greu);
		}
	printf("\n");
	for (i = 0; i < n; i++)
		{
		printf("%u ", gutui_gr[i].index);
		printf("%u ", gutui_gr[i].inalt);
		printf("%u\n", gutui_gr[i].greu);
		}*/
	/*i = 0;
	printf("%u\n", max_lost(gutui_in, 1, &i, n, u, h, cules));
	for (j = 0; j < n; j++) printf("%d", cules[j]);
	printf("\n"); 
	printf("%u\n", max_lost(gutui_in, 2, &i, n, u, h, cules));
	for (j = 0; j < n; j++) printf("%d", cules[j]);*/
	
	unsigned int pas = 1, max1, max2, max3, k;
	i = 0;
	j = 0;
	while (j < n) 
		if (cules[gutui_gr[j].index] == 1) j++;
			else
			{
			
			max1 = 0;
			max2 = 0;
			max3 = 0;
			max1 = max_lost(gutui_in, pas, &i, n, u, h, cules);
			//printf("max1 = %u\n", max1);
			//printf("j = %u\n", j);
			while ((cules[gutui_gr[j].index] == 1)&&(j < n)) j++;
			//printf("j = %u\n", j);
			if (j < n) {
				max2 = gutui_gr[j].greu;
				//printf("max2 = %u\n", max2); 
				k = j + 1;
				while ((cules[gutui_gr[k].index] == 1)&&(k < n)) k++;
				if (k < n) max3 = gutui_gr[k].greu;
				//printf("max3 = %u\n", max3); 
				   }
			
				
			if (max1 > max3) max = max + max1;
					else
					{
					max = max + max2;
					if (j < n) cules[gutui_gr[j].index] = 1;
					}
					 
			pas = pas + 1;
			}
		     	
	//printf("%d\n", max);
	//for (j = 0; j < n; j++) printf("%d", cules[j]);	
	f = fopen("gutui.out","w");
	fprintf(f,"%d\n", max);
	fclose(f);

return 0;
}