Cod sursa(job #435469)

Utilizator petreanuandiPetreanu Adelin Andrei petreanuandi Data 7 aprilie 2010 15:05:00
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.73 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100000
FILE *fin, *fout;
unsigned long int n,h,u;
unsigned long int hg[N], g[N];
unsigned long int level[1000][1000];
int dimens[N],s=0;
int alegere(int pas)
{


	unsigned long int maxh=0,maxg=0;
	int i,ales=0,aux=0;
	while(dimens[pas]==0)
	{
		pas--;
	}
	for(i=0;i<dimens[pas];i++)
		if( maxg < g[level[pas][i]] ) 
		{	maxg=g[level[pas][i]];
			aux=i;
		}
	for(i=0;i<n;i++)
		hg[i]=hg[i]+u;		
	ales=maxg;
	g[level[pas][aux]]=-1;
	printf("alesul la nivelul %d este %d \n",pas,ales);
	return ales;
}
int endofbranch(int pas)
{
	int i;
	for(i=0;i<dimens[pas];i++)
		if( g[level[pas][i]] >0 ) return 0;
	return 1;


}
int pasvalabil(int pas)
{
	int i;
	for(i=0;i<pas;i++)
		if( hg[level[pas][i]] <= h) return 1;
	return 0;

}
int haccesibil(int pas)
{
	int i;
	for(i=0;i<pas;i++)
		if(dimens[i]>0)	return 1;
	return 0;
}
int main(void) {
	fin = fopen("gutui.in", "r");
	fout = fopen("gutui.out", "w");
	int i,j;
	fscanf(fin, "%lu %lu %lu", &n, &h, &u);
	printf("%lu %lu %lu\n \n",n,h,u);
	int niv=(int) (h / u) + 1;

	
	int k,h;
	
	for(i=0;i<niv;i++)
		dimens[i]=0;

	
	for (i = 0; i < n; i++) {
		fscanf(fin, "%lu %lu", &hg[i], &g[i]);
		h=(int) (hg[i]/u) ;
		level[h][dimens[h]++] = i;
		printf("%lu %lu \n", hg[i], g[i]);
	}
	for(i=0;i<niv;i++)
	{
		printf("nivelul %d ",i);
		for(j=0;j<dimens[i];j++)
			printf("(%lu - %lu)",level[i][j],g[level[i][j]]);
		printf("\n");
	}
	printf("dimanesiune pas \n");
	for(i=0;i<niv;i++)
		printf("%d ",dimens[i]);
	printf("\n \n");
	int ales,pas;
	pas=niv-1;
	unsigned long int suma=0;
	while(haccesibil(pas))
	{
		printf("pasul %d \n",pas);
		
		
		 ales=alegere(pas);
		 if(ales>0) suma=suma+ales;
		 pas--;
		
	}
	fprintf(fout,"%lu\n",suma);		
	fclose(fin);
	fclose(fout);
	return 0;
}