Cod sursa(job #463075)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 15:05:05
Problema Gutui Scor 40
Compilator c Status done
Runda teme_upb Marime 1.52 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

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


int main (){ 

	FILE *in,*out;
	in=fopen("gutui.in","r");
	out=fopen("gutui.out","w");
	
	int N,H,U,total=0;
	fscanf(in,"%d%d%d",&N,&H,&U);
	//cumpe urmatoarele N - linii se afla gutuile, vom aloca
	//memorie pentru N structuri de tip gutuie 

	gutuie *gutui,aux1;
	gutui=(gutuie*)malloc(N*sizeof(gutuie));
	
	
	//acum citim din fisierul de intrare
	int i,j;
	for(i=0;i<N;i++){
		fscanf(in,"%d%d",&gutui[i].h,&gutui[i].g);
		
	}

	int gasit;
	
	do{
	gasit=0;
	for(i=0;i<N-1;i++)
	  if(gutui[i].g < gutui[i+1].g){
		aux1=gutui[i];
		gutui[i]=gutui[i+1];
		gutui[i+1]=aux1;
		gasit=1;
	}}
	while(gasit);

	do{
	gasit=0;
	for(i=0;i<N-1;i++)
	 if(gutui[i].g == gutui[i+1].g)
		if(gutui[i].h < gutui[i+1].h){
			aux1=gutui[i];
			gutui[i]=gutui[i+1];
			gutui[i+1]=aux1;
		gasit=1;
	}}while(gasit);

	for(i=0;i<N;i++)
		printf("%d-%d \n",gutui[i].h,gutui[i].g);

	//initializam vectorul aux

	int aux[100];
	for(i=0;i<100;i++)
		aux[i]=0;

	//cautam pentru fiecare gutuie daca ea se culege sau nu
	int pas;
	for (i=0;i<N;i++){
		//calculam pas pt gutuie
		pas=(H-gutui[i].h)/U + 1;
		//ne uitam dak in vect auxiliar pe poz pas este 0 , dak nu coboram pana cand gasim un elem 0 sau daca nu acea gutuie se ignora

		if(aux[pas] == 0){ total+=gutui[i].g; aux[pas]=1;
		}
		else
		for(j=pas-1;j>0;j--)
			if(aux[j] == 0){ total+=gutui[i].g; aux[j]=1; j=0;
			}
	}
	
	fprintf(out,"%d\n",total);
	
	free (gutui);
	fclose(in);
	fclose(out);
	return 0;
	}