Cod sursa(job #435436)

Utilizator mataevsMatei Chiperi mataevs Data 7 aprilie 2010 14:40:37
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.26 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
	unsigned int ht;
	unsigned int g;
	int ns;
}elem;

int comp(const void *a, const void *b){
	elem *p1 = (elem*)a;
	elem *p2 = (elem*)b;
	if (p1->g < p2->g)
		return 1;
	if (p1->g > p2->g)
		return -1;
	return 0;
}

int main(){
	unsigned int n,h,u;
	int i,j;
	elem *gutui, *p;
	char *secv;
	int two[32];
	int logr,expr;
	int g = 0;
	
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin,"%d %d %d",&n,&h,&u);
	gutui = (elem*)malloc(n * sizeof(elem));
	for (p = gutui, i = 0; i < n; i++, p++){
		fscanf(fin,"%d %d", &(p->ht), &(p->g));
		p->ns = (h - p->ht) / u + 1;
	}
	fclose(fin);
	
	qsort(gutui, n, sizeof(elem),comp);
	
	secv = (char*)malloc((n + 1) * sizeof(char));
	memset(secv, 0, (n + 1) * sizeof(char));
	memset(two,0,32 * sizeof(int));
	
/*	for (p = gutui, i = 0; i < n; i++, p++)
		printf("(%d, %d) ",p->g, p->ns);
	printf("\n");*/
	
	for (p = gutui, i = 0; i < n; i++, p++){
		if (p->ns >= n)// poate fi ultima gutuie luata
			g += p->g;
		else{
			logr = (ceil(log((double)p->ns)));
			if (p->ns > 1 << logr)
				logr++;
			if (logr > 0){//nu este prima gutuie care trebuie luata
				for (expr = 1 << (logr - 1), j = p->ns; j > expr; j--)//verifica pe intervalul ([log p->ns],p->ns)
					if (*(secv + j) == 0){
						*(secv + j) = 1;
						two[logr]++;
						g += p->g;
						break;
					}
				if (j == expr){//nu a reusit sa insereze in intervalul precedent
					for (logr--; logr >= 0 && two[logr] == ((logr != 0)?(1 << (logr - 1)):1); logr--);//cauta primul interval cu elemente libere
					if (logr >= 0){//a gasit un interval cu elemente libere
						for (j = 1 << logr; j > ((logr != 0)?(1 << (logr - 1)):0) && *(secv + j) == 1; j--);//cauta primul element liber
						*(secv + j) = 1;
						two[logr]++;
						g += p->g;
					}
				}
			}
			else//este prima  gutuie care trebuie luata
				if (*(secv + 1) == 0){//verifica daca poate fi luata prima
					*(secv + 1) = 1;
					two[0]++;
					g += p->g;
				}
		}
/*		for (j = 0; j < n; j++)
			printf("%d ",*(secv + j));
		printf("\n");*/
	}
	free(secv);
	free(gutui);
	
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%d\n", g);
	fclose(fout);
	return 0;
}