Cod sursa(job #440566)

Utilizator andreea149Andreea Pintilie andreea149 Data 12 aprilie 2010 09:07:56
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.47 kb
//Pintilie Andreea 321CA
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void merge(int* a, int* b,int * v, int low, int high, int mid, int N){
int i, j, k, *c, *d,*f;
	c = (int * )malloc(N * sizeof(int) );
	d = (int * )malloc(N * sizeof(int) );
	f = (int * )malloc(N * sizeof(int) );
	i = low;
	j = mid+1;
	k = low;
		while( (i <= mid) && (j <= high) ){
				if(a[i] > a[j]){
					c[k] = a[i];
					d[k] = b[i];	
					f[k] = v[i];
					k++;
					i++;
				}
				else{
					c[k] = a[j];
					d[k] = b[j];
					f[k] = v[j];
					k++;
					j++;
				}
		}
		
		while(i <= mid){
			c[k] = a[i];
			d[k] = b[i];
			f[k] = v[i];
			k++;
			i++;
		}
		
		while(j <= high){
			c[k] = a[j];
			d[k] = b[j];
			f[k] = v[j];
			k++;
			j++;
		}
		for(i = low; i < k; i++){
			a[i] = c[i];
			b[i] = d[i];
			v[i] = f[i];
		}
free(c);
free(d);	
free(f);
} 

void mergesort(int* a, int * b,int* v, int low, int high, int N){
int mid;
	if(low < high){
		mid = (low+high)/2;
		mergesort(a,b,v, low, mid,N);
		mergesort(a,b,v, mid+1, high,N);
		merge(a,b,v, low, high, mid,N);
	}
}
int main(){
FILE *fin, *fout;

	fin = fopen("gutui.in", "r");
	fout = fopen("gutui.out", "w");

int N, H, U, *h, *g, i, Gmax = 0, j, *v, *suma;
//citeste nr de gutui	
	fscanf(fin,"%d",&N);

//citeste inaltimea maxima
	fscanf(fin,"%d",&H);
	
//citeste cu cat se ridica
	fscanf(fin,"%d",&U);

//aloca memorie pentru inaltimi si greutati	
	h = (int * )malloc(N * sizeof( int ) );
	g = (int * )malloc(N * sizeof( int ) );
	v = (int * )malloc(N * sizeof( int ) );
	
//citeste inaltimile si greutatile	 
	for(i = 0; i < N; i++){
		fscanf(fin,"%d",&h[i]);
		fscanf(fin,"%d",&g[i]);
		if(h[i]%2 == 0){
			v[i] = H/U - (h[i]-1)/U - 1;
		}
		else{
			v[i] = H/U - h[i]/U - 1;
		}
	}
	int max = 0;
	for(i = 0; i < N; i++){
		if(v[i] > max){
			max = v[i];
		}
	}
	
	if(N > max){
		max = N;
	}
suma = (int *)malloc(max * sizeof(int));
//1 1 3 2 3 2 2 2 1
//sorteaza in functie de greutate
mergesort(g,h,v,0,N-1,N);

//afiseaza in fisierul de iesire ce a citit sortat in functi de inaltime

for(i = 0; i < max; i++)
{suma[i] = 0;}

	for(i = 0; i < max; i++){
		if(suma[v[i]] == 0){
			suma[v[i]] = g[i];
		}
		else{
				j = v[i];
				while(j >= 0 ){
					if(suma[j] == 0){
						suma[j] = g[i];
						j = -1;
					}
					else{
						j=j-1;
					}
					
				}
		}	
	} 
	
//calculeaza Gmax adunand suma	
	for(i = 0; i < max; i++){
		if(suma[i] != 0){
		Gmax = suma[i] + Gmax;
		}
	}
	
	fprintf(fout,"%d\n",Gmax);
free(h);
free(g);
fclose(fin);
fclose(fout);
return 0;
}