Cod sursa(job #438663)

Utilizator TokPhobiaCosoi Andrei TokPhobia Data 10 aprilie 2010 22:35:09
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.51 kb
#include <stdio.h>
#include <stdlib.h>

#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT 4294967295
#define NMAX 100002

typedef struct gutuie {
	int g, h;
	gutuie *next;
} gutuie;

typedef struct elem {
	unsigned int val;
	elem *next;
} elem;

int insert(elem *start, gutuie *gutui, int h, int u) {
	unsigned int nivel_maxim_gutuie = (h-gutui->h)/u;
	int out_of_bounds = 0;
	
	elem *p = start->next, *previous = start, *nou;
	
	//parcurgem de la final toate gutuile puse pana atunci
	while (p) {
		
		//daca gutuia curenta poate fi pusa mai tarziu decat gutuia noua
		if (p->val >= nivel_maxim_gutuie) {
			
			//trecem la urmatoarea gutuie
			if (p->val == nivel_maxim_gutuie) {
				if (nivel_maxim_gutuie)
					nivel_maxim_gutuie--;
				else
					out_of_bounds = 1;
			}
			previous = p;
			p = p->next;
			
		}
		
		//daca am ajuns la punctul la care am putea sa adaugam, verificam daca se poate
		else { 
			
			//daca o putem adauga
			if ((previous->val - nivel_maxim_gutuie) && (nivel_maxim_gutuie - p->val) && nivel_maxim_gutuie >= 0) {
				
				//adaugam noua gutuie intre previous si p
				nou = (elem*)malloc(sizeof(elem));
				nou->val = nivel_maxim_gutuie;
				nou->next = p;
				previous->next = nou;
				return 1;
				
			}
			
			//daca nu se poate adauga
			else 
				return 0;
			
		} //end verificare si adaugare
		
	}//end while
	
	
	//daca am ajuns pana aici inseamna ca ar trebui sa incercam la inceputul listei
	if ((previous->val - nivel_maxim_gutuie) && !out_of_bounds) {
		
		nou = (elem*)malloc(sizeof(elem));
		nou->val = nivel_maxim_gutuie;
		nou->next = previous->next;
		previous->next = nou;
		return 1;
		
	}

	return 0;
}

int comparator(const void * a, const void * b) {
	return -1*(((gutuie*)a)->g - ((gutuie*)b)->g);
}

int main() {
	
	FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
	int n, h, u, i;
	long int totalsum = 0;
	gutuie gutui[NMAX];
	elem *start;
	
	//citim datele intr-o lista de gutui
	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	for (i=0; i<n; i++)
		fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
	//sfarsit citit date
	
	//sortam datele
	qsort(gutui, n, sizeof(gutuie), comparator);
	
	//initializam lista de gutui care le culegem
	start = (elem*)malloc(sizeof(elem));
	start->val = INFINIT;
	start->next = NULL;
	
	//luam gutuile in ordinea descrescatoare a greutatii
	for (i=0; i<n; i++)
		//vedem daca putem pune gutuia maxima in lista
		if (insert(start, &gutui[i], h, u))
			totalsum += gutui[i].g;
	
	fprintf(fout, "%ld\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}