Cod sursa(job #437285)

Utilizator anaitsircVoicu Cristiana anaitsirc Data 9 aprilie 2010 16:09:51
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.51 kb
#include <stdlib.h>
#include <stdio.h>


typedef struct{
	int h;
	int g;
}gutuie;

/*void Sort_Shell (gutuie v[], int dim){
	int i, pas, inv;
	gutuie a;
	pas = dim;
	while (pas >1 )
		{
		pas=pas/2 ;	
		do
			{
			inv=0 ; 			
			for (i=0; i < dim-pas; i++)
				{			
				if (v[i].g < v[i+pas].g)		//sortare descresactoare a greutatilor gutuilor
					{
					a=v[i+pas];
					v[i+pas]=v[i];
					v[i]=a;
					inv=1;		
				
					}
				}
			} while (inv);
		}
}
*/
void sort_met_bulelor (gutuie a[], int n){
	gutuie x;
	int i, j;
	for (i=0; i<n; i++){
		
		for (j=i+1; j<n; j++){
			
			if (a[i].g < a[j].g){
				x=a[j];
				a[j]=a[i];
				a[i]=x;
				
			}
			
		}
	}
}
int main(){
gutuie sir[100000];
int i;
FILE *fp=fopen("gutui.in","r");
FILE *fp1=fopen("gutui.out","w");
char s[80];
fgets(s,80,fp);

char *sep=" ";
int N=atoi(strtok (s,sep));

int H=atoi(strtok (0,sep));

int U=atoi(strtok (0,sep));

int n=0;
while ( fgets(s,80,fp) != NULL ){
	sir[n].h=atoi(strtok (s,sep));
	sir[n].g=atoi(strtok (0,sep));

	n++;
}//end while

fclose (fp);
int g=0;
sort_met_bulelor(sir,N);
//Sort_Shell(sir,N);
//for( i=0; i<N;i++)
	//printf("%d %d\n", sir[i].h, sir[i].g);

int a[H/U+1];
for (i=1; i<=H/U; i++)
	a[i]=0;
for( i=0; i<N;i++){
	
	n=(H-sir[i].h)/U+1;
	while ((a[n]!=0) && (n>0))
		n--;
	//printf("%d     ",n);
	if (n!=0) 
		a[n]=sir[i].h;
			
}

for (i=1; i<=H/U; i++){
	//printf("%d %d\n",a[i], sir[i-1].g);
	if (a[i]!=0)
		g=g+sir[i-1].g;
}

	
//printf("%d \n",g);
fprintf(fp1,"%d",g);
fclose(fp1);
}