Cod sursa(job #133615)

Utilizator megabyteBarsan Paul megabyte Data 9 februarie 2008 10:25:02
Problema Lapte Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#define INF "lapte.in"
#define OUF "lapte.out"
#define DBG_OFF
using namespace std;
const short NMAX=128;

short n,m,a[NMAX],b[NMAX];
short best[NMAX][NMAX],sol[NMAX][NMAX],t;//best[i][j]-nr maxim de litri b daca primi i beau j l de lapte a 

short solgen(short tp)//pentru timpul partial tp
{
	short i,j,k,nrb,tr,tk[NMAX];
	for(j=0;j<NMAX;++j){ best[0][j]=-1;sol[0][j]=0;}
	best[0][0]=0;

	for(i=1;i<=n;++i) tk[i]=tp/a[i];//printf("%hd ",tk[i]);}


	for(i=1;i<=n;++i)
	  for(j=0;j<=m;++j)
	  {
		  best[i][j]=-1;
		  sol[i][j]=0;
		  for(k=0;k<=tk[i]&&k<=j;++k) //daca persoana i bea k litri din a
		  if(best[i-1][j-k]>=0)	  
		  {
			  tr=(tp-k*a[i]);// timp ramas pt b
			  nrb=tr/b[i];// nr de litri b 
			  if(tr>=0&&best[i-1][j-k]+nrb>best[i][j])
			  {
				  best[i][j]=best[i-1][j-k]+nrb;
				  sol[i][j]=k;
			  }
		  }
//		  k=sol[i][j];tr=(tp-k*a[i]);
//		  printf("%hd %hd %hd %hd\n",i,j,best[i][j],tr); 
		  
	  }

	nrb=best[n][m];//pozitie si timp

	if(nrb>=m) return 1;
	return 0;
}

void recon(short i,short j,FILE *fp)
{
	if(i>0)
	{
		if(j-sol[i][j]>=0) recon(i-1,(j-sol[i][j]),fp);
		fprintf(fp,"%hd %hd\n",sol[i][j],(t-sol[i][j]*a[i])/b[i]);
	}
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	short i,j,st,dr,mij;
	fscanf(in,"%hd%hd",&n,&m);
	for(i=1;i<=n;++i) fscanf(in,"%hd%hd",a+i,b+i);

#ifdef DBG_ON
	printf("tp=");scanf("%hd",&t);
	printf("solgen:%hd\n",solgen(t));
	for(i=0;i<=m;++i) printf("%hd ",i);
	printf("\n\n");
	for(i=0;i<=n;++i)
	{
		for(j=0;j<=m;++j) printf("%hd ",best[i][j]);
		printf("\n");
	}
	recon(n,m,stdout);
#endif
	st=1;dr=100;t=100;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(solgen(mij))
		{
			dr=mij-1;
			t=mij;
		}
		else st=mij+1;
	}

	solgen(t);
	fprintf(out,"%hd\n",t);
	recon(n,m,out);
	fclose(in);fclose(out);
	return 0;
}