Cod sursa(job #440949)

Utilizator skyzthalimitBazdragan Alexandru Gabriel skyzthalimit Data 12 aprilie 2010 18:08:17
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 4.36 kb
#include <stdio.h>
#include <stdlib.h>

long int *height, *kg, *lvl, *nr, collected = 0, forbidden = 0, sum = 0;		//collected va retine numarul de gutui culese intrun anumit moment, forbidden numarul de gutui innacesibile
long int aux = 0, aux2 = 0, i_aux = -1;
unsigned char *bad;

void quickSort (long int v[], long int a[], long int b[], long int lo, long int hi){		//functiea de sortare, v este vectorul principal dupa care se efectuaza sortarea
    	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){			//numara cate gutui de aceeasi greutate sunt intre indicii k si N-1
	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){		//numara cate gutui de aceeasi greutate se afla la acelasi nivel intre indicii k si N-1
	int i, nr = 2;
	i = k;
	do{	
		i++; 
		if(v[k] == v[i] && l[k] == l[i]){
			nr++;
		}
		else return nr;
	}while(i<N);
	return nr;
}	

void take(long int i){					//functie care face "culegerea" unei gutui i
	sum = sum + kg[i];
	//printf("ia i = %ld, -> height = %ld, kg = %ld, lvl = %ld, nr = %ld\n", i, height[i], kg[i], lvl[i], nr[i]);
	forbidden++;
	lvl[i] = -1;
	bad[i] = 1;
	collected++;
	
}

int main(){
	long int i, j, k, num, current, start, end, to_take, N, H, U;
	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;
	}
	fclose(fp_in);
	
	quickSort(kg, height, lvl, 0, N-1);				//se sorteaza vectorul dupa greutate descrescator
	
	i = 0;	
	while(i<(N-1)){							//se sorteaza inaltimile pentru fiecare greutate fara a tine cont de lvl
		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)){							//se numara gutuile care au aceasi greutate si se afla la acelasi lvl
		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++;
	}
	
	start = 0; end = N;
	i = start;
	to_take =  start;	
	do{					
		if(aux < (nr[i]-1) && bad[i] == 0){
			i_aux = i + 1;
			aux2 = aux + nr[i] - 1;
		}
		if(i == i_aux){
			aux = aux2;
		}			
		current = lvl[i] - collected - aux;
	//	printf("i = %ld -> current = %ld :: aux = %ld\n", i, current, aux);
		if(current >= 0){
			if(current == (nr[i] - 1)){
				for(j=(i+nr[i]-1) ; j>=i ; j--){
					take(j);
					if(j == end-1){
						end--;
					}
				}
				if(i == start){
					start++;
				}
				i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
			}
			else if(current == 0){
				take(i);
				if(i == start){
					start++;
				}
				if(i == end-1){
					end--;
				}
				i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
			}
			else{ 
				if(i == (end-1)){
					if(to_take == start){
						take(start);
						start++;
						to_take++;
						i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
					}
					else {
						i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
						to_take = start;
					}
				}
				else i++;
				
			}
		}
		else{
			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){
					take(start);
					start++;
					to_take++;
					i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
				}
				else {
					i = start;	aux = 0; 	aux2 = 0; 	i_aux = -1;
					to_take = start;
				}
			}
		}
	}while(forbidden < N);	
	
	fp_out = fopen("gutui.out", "w");
	fprintf(fp_out, "%ld\n", sum);	
	fclose(fp_out);
	return 0;
}