Cod sursa(job #435675)

Utilizator violeta.marinVioleta Marin violeta.marin Data 7 aprilie 2010 19:12:10
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>

struct gut{
	unsigned int level;	
	unsigned int weight;
	};

struct gut *gutui;

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



int main(){
	unsigned int i, j, k;
	unsigned int h,u,n;	
	unsigned int height,no_levels, min_height = 0xffffffff;
	unsigned int *schedule;
	unsigned int max = 0;
	
	FILE *f = fopen("gutui.in","r");
	fscanf(f, "%u", &n);
	fscanf(f, "%u", &h);
	fscanf(f, "%u", &u);
	
	
	/*
	printf("n = %u h = %u u = %u\n", n ,h,u);
	printf("%u\n", h/u);
	*/
	gutui = (struct gut *)malloc(n * sizeof(struct gut));
	
	for (i = 0; i < n; i++)
		{
		fscanf(f, "%u", &height);
		fscanf(f, "%u", &gutui[i].weight);
		gutui[i].level = (h - height)/u + 1 ;
		if (min_height > height) min_height = height;
		}
	fclose(f);

	qsort(gutui, n, sizeof(struct gut), compare);
	
	
	/*for (i = 0; i < n; i++)
		{
		printf("%u ", gutui[i].weight);
		printf("%u \n", gutui[i].level);
		}
	printf("\n");*/
	
	
	no_levels = (h - min_height)/u + 1;
	schedule = (unsigned int *) calloc(no_levels + 1, sizeof(unsigned int));

	for (i = 0; i < n; i++)
		for (j = no_levels; j > 0; j--)
			if ((schedule[j] == 0)&&(j <= gutui[i].level))
				{
				//printf("max = %u\n", max);
				max = max + gutui[i].weight;
				//printf("max = %u\n", max);
				schedule[j] = i + 1;
				break; 
				}  
	/*for (i = 0; i <= no_levels; i++)
		printf("%u ", schedule[i]);
	printf("\n");
	//printf("%u\n", max);
	/*
	printf("no_levels = %u\n", no_levels);
	*/
	f = fopen("gutui.out", "w");
	fprintf(f, "%u\n", max);
	fclose(f);

 
return 0;
}