Cod sursa(job #433818)

Utilizator TokPhobiaCosoi Andrei TokPhobia Data 4 aprilie 2010 14:04:25
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 3.16 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT -999999
#define DISPLAY 0

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

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

int insert(elem *start, gutuie gutui, int u) {
	elem *p = start->next, *previous = start, *nou;
	
	//parcurgem de la final toti maximii alesi pana atunci
	while (p) {
		if (DISPLAY) { printf("Suntem la gutuia de inaltime %d. Comparam cu %d. ", p->val, gutui.h); fflush(stdout); }
		//daca elementul curent e mai jos decat ce adaugam
		if (p->val < gutui.h) {
			if (DISPLAY) { printf("Gutuia curenta e mai jos. Trecem la urmatoarea\n"); fflush(stdout); }
			//trecem la urmatorul element
			previous = p;
			p = p->next;
		}
		//daca am ajuns la punctul la care am putea sa adaugam, verificam daca se poate
		else if (ceil((float)gutui.h/u) - ceil((float)p->val/u)) {
			if (DISPLAY) { printf("Gutuia curenta e deasupra gutuii pe care incercam sa o adaugam. Incercam s-o bagam pe cea noua\n"); fflush(stdout); }
			//daca nu suntem la capatul listei
			if (p->next) {
				nou = (elem*)malloc(sizeof(elem));
				nou->val = gutui.h;
				nou->next = p->next;
				p->next = nou;
				return 1;
			}
			else { //daca suntem la capatul listei
				nou = (elem*)malloc(sizeof(elem));
				nou->val = gutui.h;
				nou->next = p->next;
				p->next = nou;
				return 1;
			}
		}
		else {
			if (DISPLAY) { printf("Nu am putut adauga gutuia noua (nu indeplinea conditiile)\n"); fflush(stdout); }
			return 0;
		}
	}
	if (DISPLAY) { printf("Incercam sa adaugam gutuia la inceputul listei (nivelele sunt %f si %d)... ", ceil((float)gutui.h/u), previous->val/u); fflush(stdout); }
	if (ceil((float)gutui.h/u) - ceil((float)previous->val/u)) {
		if (DISPLAY) { printf("OK\n"); fflush(stdout); }
		nou = (elem*)malloc(sizeof(elem));
		nou->val = gutui.h;
		nou->next = previous->next;
		previous->next = nou;
		return 1;
	}
	if (DISPLAY) { printf("Nu a mers\n"); fflush(stdout); }
	return 0;
}

int main() {
	
	FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
	int n, h, u, i, j, max, maxpoz, totalsum = 0;
	gutuie gutui[500];
	
	elem *start;
	
	start = (elem*)malloc(sizeof(elem));
	start->val = INFINIT;
	start->next = NULL;
	
	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	for (i=1; i<=n; i++)
		fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
	
	//gasim gutuia cu greutatea maxima de n ori
	for (i=1; i<=n; i++) {
		
		max = -1;
		maxpoz = 0;
		
		//luam urmatoarea gutuie maxima
		for (j=1; j<=n; j++)
			if (max < gutui[j].g) {
				max = gutui[j].g;
				maxpoz = j;
			}
		
		if (DISPLAY) { printf("Incerc sa adaug (%d, %d) la lant. ", gutui[maxpoz].g, gutui[maxpoz].h); fflush(stdout); }
		
		//vedem daca putem pune gutuia maxima in lista
		if (insert(start, gutui[maxpoz], u)) {
				
			if (DISPLAY) { printf("Am adaugat gutuia\n"); fflush(stdout); }
				
			totalsum += gutui[maxpoz].g;
			
		}
		else if (DISPLAY) { printf("Nu am adaugat gutuia\n"); fflush(stdout); }
		
		if (DISPLAY) printf("Suma partiala %d\n", totalsum);
		
		gutui[maxpoz].g = -1;
	}
	
	if (DISPLAY) printf("%d\n", totalsum);
	
	fprintf(fout, "%d\n", totalsum);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}