Cod sursa(job #434584)

Utilizator violeta.marinVioleta Marin violeta.marin Data 6 aprilie 2010 03:16:35
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.94 kb
#include <stdio.h>
#include <stdlib.h>


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

int compare (const void * a, const void * b)
{
  //return ( *(int*)a - *(int*)b );
	return -((*(struct gut*)a).inalt - (*(struct gut*)b).inalt); 	
}

	
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));
	for (i = 0; i < n; i++)
		{
		fscanf(f, "%u", &gutui[i].inalt);
		fscanf(f, "%u", &gutui[i].greu);
		}

	qsort(gutui, n, sizeof(struct gut), compare);
	/*for (i = 0; i < n; i++)
		{
		printf("%u ", gutui[i].inalt);
		printf("%u\n", gutui[i].greu);
		}*/
	fclose(f);

	i = 0;
	j = 0;
	int ult_indice, k;
	while ( i < n){
		/*while ((gutui[i].greu == 0) && ( i < n)) 
			i++;
		if ( i == n) break;*/
		gr = gutui[i].greu;
		gutui[i].greu = 0;
		ult_indice = i;
		if (gutui[i].inalt + u < h) 
		{
		
		max = max + gr;
		for ( j = i; j < n; j++)
			gutui[j].inalt = gutui[j].inalt + u;
		i++;
		}		
		/*if (gutui[i].inalt + u < h)
			{
			
			for ( j = i + 1; j < n; j++)
				if (gr < gutui[j].greu)
					{
					gutui[ult_indice].greu = gr;
		 			gr = gutui[j].greu;
					ult_indice = j;
					gutui[j].inalt = gutui[j].inalt + u;
					gutui[j].greu = 0;
					}
			max = max + gr;
			if (gr == 0) break;
			}*/
		else	{
			gutui[i].inalt = gutui[i].inalt + u;
			k = 0;		
			for ( j = i + 1; j < n; j++) {
				if ((gr < gutui[j].greu) && (gutui[j].inalt + u > h))
					{
					gutui[ult_indice].greu = gr;
					gr = gutui[j].greu;
					ult_indice = j;
					//i = j + 1;
					gutui[j].inalt = gutui[j].inalt + u;
					gutui[j].greu = 0;
					}
				if ((gutui[j].inalt + u < h)&&( k == 0)) 
					 				k = j;
							}
			max = max + gr;
			i = k;
			}				 			
			} 		
		//printf("%d\n", max);	
		     	
	//printf("%d\n", max);
	f = fopen("gutui.out","w");
	fprintf(f,"%d\n", max);
	fclose(f);

return 0;
}