Cod sursa(job #437683)

Utilizator funke_shitVatamanu Daniela funke_shit Data 10 aprilie 2010 00:09:59
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.64 kb
#include <stdio.h>
#include <malloc.h>

#define u_int unsigned int


void merge(u_int **a, int low, int high, int mid){
	int i, j, k;
	u_int **c;
	
	c = (u_int**)malloc((high+1)*sizeof(u_int*));
	for(i = 0; i < high+1; i ++)
		c[i] = (u_int*)malloc(2*sizeof(u_int));
		
	i = low;
	j = mid+1;
	k = low;
	
	while((i <= mid) && (j <= high)){
		if(a[i][0] > a[j][0]){
			c[k][0] = a[i][0];
			c[k][1] = a[i][1];
			i ++;
		}
		else{
			c[k][0] = a[j][0];
			c[k][1] = a[j][1];
			j ++;
		}
		k ++;
	}
	while(i <= mid){
		c[k][0] = a[i][0];
		c[k][1] = a[i][1];
		k ++;
		i ++;
	}
	
	while(j <= high){
		c[k][0] = a[j][0];
		c[k][1] = a[j][1];
		k ++; 
		j ++;
	}
	
	for(i = low; i < k; i ++){
		a[i][0] = c[i][0];
		a[i][1] = c[i][1];
	}
	
	for(i = 0; i < high+1; i ++)
		free(c[i]);
	free(c);
	
	return;
}

void merge_sort(u_int **a, int low, int high){
	int mid;
	if(low<high){
		mid = (low+high)/2;
		merge_sort(a, low, mid);
		merge_sort(a, mid+1, high);
		merge(a, low, high, mid);
	}
	return;
}

int main(){
	FILE *f, *g;
	f = fopen ("gutui.in", "r");
	g = fopen ("gutui.out", "w");
	u_int H, U, **a, cules = 0, *momentan, h_mom;
	int N, i, j, l_mom = 0, k, n, p = 0;
	
	fscanf(f, "%d %u %u", &N, &H, &U);
	n = N;
	a = (u_int**)malloc(N*sizeof(u_int*));
	momentan = (u_int*)malloc(N*sizeof(u_int*));
	for(i = 0; i < N; i ++){
		a[i] = (u_int*)malloc(2*sizeof(u_int));
		fscanf(f, "%u %u", &a[i][0], &a[i][1]);
	}

//merge_sort descrescator		
	merge_sort(a, 0, N-1);
	
	/*for(i = 0; i < N; i ++)
		fprintf(g, "%u %u\n", a[i][0], a[i][1]);
	*/
	
//pornesc de la ultimul nivel	
	if(H%U == 0)
		h_mom = U;
	else
		h_mom = H - ((H / U) * U);
	
//incep sa "culeg" gutui, pornind de la ultimul nivel
	while((h_mom <= H) && (N > 0 || l_mom > 0)){
		if(l_mom > 0){
			cules = cules + momentan[l_mom-1];
			l_mom --;
			h_mom = h_mom + U;
		}
		else
			if(p)
				h_mom = h_mom + U;
		p = 1;
		while(N > 0){
			if(a[N-1][0] > h_mom)
				break;
			if(l_mom == 0){
				momentan[l_mom] = a[N-1][1];
				l_mom ++;
				N --;
			}
			else{
				k = 1;
				for(i = 0; i < l_mom; i ++)
					if(momentan[i] > a[N-1][1]){
						for(j = l_mom; j > i; j --)
							momentan[j] = momentan[j-1];
						l_mom ++;
						momentan[i] = a[N-1][1];
						N --;
						k = 0;
						break;
					}
				if(k){
					momentan[l_mom] = a[N-1][1];
					l_mom ++;
					N --;
				}
			}
		/*fprintf(g, "momentan: ");
		for(i = 0; i < l_mom; i ++)
			fprintf(g, "%u ", momentan[i]);
		fprintf(g, "\n\n");
		fprintf(g, "gutui: \n");
		for(i = 0; i < N; i ++)
			fprintf(g, "%u %u\n", a[i][0], a[i][1]);
		fprintf(g, "\n\n");*/
		}
	}
	
	free(momentan);
	for(i = 0; i < n; i ++)
		free(a[i]);
	free(a);
	
	fprintf(g, "%u", cules);
	
	return 0;
}