Cod sursa(job #440164)

Utilizator moroMOROSAN EMANUEL moro Data 11 aprilie 2010 22:26:11
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.13 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	int h, g, niv; 
	}gutui;

typedef struct{
	int g, niv;
	}vector;

typedef struct{
	int *g, niv, elem;
	}vector1;

void quickSort1(gutui *vect, int stanga, int dreapta) {  
	int i = stanga, j = dreapta;  
	int tmp1, tmp2, tmp3;  
	int pivot = vect[dreapta].niv;  
	while (i <= j){  
		while (vect[i].niv < pivot)  
			i++;  
		while (vect[j].niv > pivot)  
			j--;  
		if (i <= j){
            tmp1=vect[i].niv;  
			vect[i].niv=vect[j].niv;  
			vect[j].niv=tmp1;
			tmp2=vect[i].h;  
			vect[i].h=vect[j].h;  
			vect[j].h=tmp2;
			tmp3=vect[i].g;  
			vect[i].g=vect[j].g;  
			vect[j].g=tmp3;
            i++;  
            j--;  
			}  
		}  
	if (stanga < j)  
		quickSort1(vect, stanga, j);  
	if (i < dreapta)  
		quickSort1(vect, i, dreapta);  
}

void quickSort2(gutui *vect, int stanga, int dreapta) {  
	int i = stanga, j = dreapta;  
	int tmp1, tmp2, tmp3;  
	int pivot = vect[dreapta].g;  
	while (i <= j){  
		while (vect[i].g > pivot)  
			i++;  
		while (vect[j].g < pivot)  
			j--;  
		if (i <= j){
            tmp1=vect[i].niv;  
			vect[i].niv=vect[j].niv;  
			vect[j].niv=tmp1;
			tmp2=vect[i].h;  
			vect[i].h=vect[j].h;  
			vect[j].h=tmp2;
			tmp3=vect[i].g;  
			vect[i].g=vect[j].g;  
			vect[j].g=tmp3;
            i++;  
            j--;  
			}  
		}  
	if (stanga < j)  
		quickSort2(vect, stanga, j);  
	if (i < dreapta)  
		quickSort2(vect, i, dreapta);  
}

int main(){
	int n, h, u, i, j, k, nivele, dif=1, suma=0, max, t;
	gutui *gut;
	vector *vec;
	vector1 *list;
	FILE *fo, *fc;
	fo=fopen("gutui.in", "r");
	fscanf(fo,"%d%d%d", &n, &h, &u);
	gut=(gutui*)malloc(n*sizeof(gutui));
	
	nivele=h/u;
	
	for(i=0;i<n;i++){
		fscanf(fo,"%d%d", &gut[i].h, &gut[i].g);
		gut[i].niv=nivele-gut[i].h/u;
		}
	fclose(fo);
	
	/*
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].g);
	printf("\n");
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].h);
	printf("\n");
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].niv);
	printf("\n");
	printf("\n");	
	*/
	quickSort1(gut,0,n-1);
		
	i=0;
	for(j=0;j<n;j++){
		if(gut[i].niv!=gut[j].niv){
			//if(j==n-1)
			//	quickSort2(gut,i,j);
			//else
				quickSort2(gut,i,j-1);
			i=j;
			}
		}
	
	for(i=0;i<n-1;i++)
		if(gut[i].niv!=gut[i+1].niv)
			dif++;
	
	vec=(vector*)calloc((dif+n),sizeof(vector));
		
	j=0;
	k=1;
	i=0;
	vec[0].niv=gut[0].niv;
	while(i<n){
		if(vec[j].niv!=vec[j].g){
			if(gut[i].niv==vec[j].niv){
				vec[j].g++;
				vec[k].g=gut[i].g;
				vec[k].niv=gut[i].niv;
				k++;
				}
			else{
				j=k;
				vec[j].niv=gut[i].niv;	
				vec[j].g++;
				k++;
				vec[k].g=gut[i].g;
				vec[k].niv=gut[i].niv;
				k++;
				}
			i++;
			}
		else{
			while(gut[i].niv==vec[j].niv)
				i++;
			j=k;
			vec[j].niv=gut[i].niv;	
			vec[j].g++;
			k++;
			vec[k].g=gut[i].g;
			vec[k].niv=gut[i].niv;
			k++;
			i++;
			}	
		}
	
	list=(vector1*)malloc(dif*sizeof(vector1));
	
	i=0;
	k=0;
	for(k=0;k<dif;k++){
		list[k].niv=vec[i].niv;
		list[k].elem=vec[i].g;	
		list[k].g=(int*)calloc(vec[i].g,sizeof(int));
		for(j=0;j<vec[i].g;j++)
			list[k].g[j]=vec[i+j+1].g;
		i=i+vec[i].g+1;
		}
	
	//construire solutie
	j=0;	
	while(j<dif){
		t=j;
		max=list[j].g[0];
		for(i=j+1;i<dif-1;i++){
			if(list[i].niv-list[j].niv<=list[i].elem)
				if(max<list[i].g[list[i].niv-list[j].niv]){
					max=list[i].g[list[i].niv-list[j].niv];
					t=i;
					}
			}
		suma=suma+max;
		for(k=list[t].niv-list[j].niv;k<list[t].elem-1;k++)
			list[t].g[k]=list[t].g[k+1];
		for(k=0;k<dif;k++){
			if(list[k].elem==list[k].niv)
				list[k].elem-=1;
			list[k].niv-=1;
			}
		if(list[j].niv==0)
			j++;
	}
	
	/*
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].g);
	printf("\n");
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].h);
	printf("\n");
	for(i=0;i<n;i++)
		printf("%d\t", gut[i].niv);
	printf("\n");
	printf("\n");
	
	for(i=0;i<n+dif;i++)
		printf("%d\t", vec[i].g);
	printf("\n");
	for(i=0;i<n+dif;i++)
		printf("%d\t", vec[i].niv);
	printf("\n\n");
	
	for(i=0;i<dif;i++){
		for(j=0;j<list[i].elem;j++)
			printf("%d ", list[i].g[j]);
		printf("\n");
		}
	printf("suma este = %d", suma);
	*/
	free(gut);
	free(vec);
	for(k=0;k<dif;k++)
		free(list[k].g);
	free(list);
	fc=fopen("gutui.out", "w");
	fprintf(fc,"%d\n",suma);
	fclose(fc);
	return 0;	
	}