Cod sursa(job #440807)

Utilizator skyzthalimitBazdragan Alexandru Gabriel skyzthalimit Data 12 aprilie 2010 15:53:09
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.32 kb
#include <stdio.h>
#include <stdlib.h>

void quickSort (long int v[], long int a[], long int b[], long int lo, long int hi){
    	long int i, j, aux;
    	long int x;
    		
	i = lo;
	j = hi;
	x = v[(lo+hi)/2];

    	do
    	{
        	while (v[i]>x) i++;
        	while (v[j]<x) j--;
        	if (i<=j){
        	    	aux = v[i]; v[i] = v[j]; v[j] = aux;
            		aux = a[i]; a[i] = a[j]; a[j] = aux;
            		aux = b[i]; b[i] = b[j]; b[j] = aux; 
            		i++; j--;
        	}
    	}while (i<=j);

    	if (lo<j) quickSort(v, a, b, lo, j);
    	if (i<hi) quickSort(v, a, b, i, hi);
}

long int count(long int v[], long int k, long int N){
	int i, nr = 2;
	i = k;
	do{
		if(v[k] == v[++i]){
			nr++;
		}
		else return nr;
	}while(i<N);
	return nr;
}
long int count_lvl(long int v[], long int l[], long int k, long int N){
	int i, nr = 2;
	i = k;
	do{	i++;
		//printf("v = %ld lvl = %ld\n", v[i], l[i]); 
		if(v[k] == v[i] && l[k] == l[i]){
			nr++;
		}
		else return nr;
	}while(i<N);
	return nr;
}	
int main(){
	long int i, j, k, m, num, current, collected, aux, aux2, forbidden = 0, sum, start, end, to_take, N, H, U, *height, *kg, *lvl, *nr; //*bad;
	unsigned char *bad;
	FILE *fp_in, *fp_out;
	
	fp_in = fopen("gutui.in", "r");
	fscanf(fp_in, "%ld %ld %ld\n", &N, &H, &U);
	
	height = malloc(N*sizeof(long int));
	kg = malloc(N*sizeof(long int));
	lvl = malloc(N*sizeof(long int));
	nr = malloc(N*sizeof(long int));
	bad = malloc(N*sizeof(unsigned char));
	
	for(i=0 ; i<N ; i++){
		fscanf(fp_in, "%ld %ld\n", &height[i], &kg[i]);
		if(height[i] > H){
			lvl[i] = -1;
			forbidden++;
			bad[i] = 1;
		}
		else{
			lvl[i] = (H - height[i])/U;
			bad[i] = 0;
		}
		nr[i] = 1;
	//	printf("%ld %ld, %ld\n", height[i], kg[i], lvl[i]);
	}
	fclose(fp_in);
	//printf("\n");
	
	quickSort(kg, height, lvl, 0, N-1);
	
	i = 0;
	while(i<(N-1)){
		if(kg[i] == kg[i+1]){
			k = i;
			num = count(kg, (k+1), N);
			i = k + num;
			quickSort(height, kg, lvl, k, i-1);
			}
		else i++;
	}
	i = 0;
	while(i<(N-1)){
		if(kg[i] == kg[i+1] && lvl[i] == lvl[i+1]){
			k = i;
			num = count_lvl(kg, lvl, (k+1), N);
			i = k + num;
			for(j=k ; j<i ; j++){
				nr[j] = num;
			}
		}
		else i++;
	}
	
/*	for(i=0 ; i<N ; i++){
		printf("%ld %ld, %ld, sunt %ld\n", height[i], kg[i], lvl[i], nr[i]);
	}
	printf("\n");*/
	
	start = 0; end = N;
	collected = 0;
	//forbidden = 0;
	sum = 0;
	aux = 0;
	i = start;
	do{
	/*	if(aux < (nr[i] - 1)){
			m = i;
			aux2 = aux + nr[i] - 1;
		}
	/*	if(i == (m + nr[m])){
			aux = aux2;
		}*/
		current = lvl[i] - collected;
		//printf("i = %ld -> current = %ld\n", i, current);
		if(current >= 0){
			if(current == (nr[i] - 1)){
				for(j=(i+nr[i]-1) ; j>=i ; j--){
					//printf("%ld %ld, %ld, sunt %ld\n", height[j], kg[j], lvl[j], nr[j]);
					sum = sum + kg[j];
					bad[j] = 1;
					forbidden++;
					lvl[j] = -1;
					collected++;
					if(j == end-1){
						end--;
					}
				}
				if(i == start){
					start++;
				}
				i = start;
				aux = 0;
			}
			else if(current == 0){
				//printf("%ld %ld, %ld, sunt %ld\n", height[i], kg[i], lvl[i], nr[i]);
				sum = sum + kg[i];
				bad[i] = 1;
				forbidden++;
				lvl[i] = -1;
				collected++;
				if(i == start){
					start++;
				}
				if(i == end-1){
					end--;
				}
				i = start;
				aux = 0;
			}
			else{ 
				if(i == (end-1)){
					if(to_take == start){
						//printf("%ld %ld, %ld, sunt %ld\n", height[start], kg[start], lvl[start], nr[start]);
						sum = sum + kg[start];
						bad[start] = 1;
						forbidden++;
						lvl[start] = -1;
						collected++;
						start++;
						to_take++;
						i = start;
						aux = 0;
					}
					else {
						i = start;
						to_take = start;
						aux = 0;
					}
				}
				else i++;
				
			}
		}
		else{	//printf("aici nu intra\n");
			if(i != (end-1)){
				if(bad[i] == 0){
					bad[i] = 1;
					forbidden++;
				}
				i++;
			}
			else {
				if(bad[i] == 0){
					bad[i] = 1;
					forbidden++;
				}
				if(to_take == start){
					sum = sum + kg[start];
					forbidden++;
					lvl[start] = -1;
					collected++;
					start++;
					to_take++;
					i = start;
					aux = 0;
				}
				else {
					i = start;
					to_take = start;
					aux = 0;
				}
			}
		}
		//printf("start = %ld, end = %ld, forbidden = %ld, collected = %ld\n", start, end, forbidden, collected);
	}while(forbidden < N);	
	
	fp_out = fopen("gutui.out", "w");
	fprintf(fp_out, "%ld\n", sum);	
	fclose(fp_out);
	return 0;
}