Cod sursa(job #132005)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 4 februarie 2008 20:58:39
Problema Lapte Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
FILE*fin=fopen("lapte.in","r");
FILE*fout=fopen("lapte.out","w");
#define maxn 201
#define min(a,b)((a)<(b)?(a):(b))
int n,l,a[maxn],b[maxn],p[maxn][maxn],wf[maxn][maxn];
int posibil(int t)
{
  int i,j,k,bj,pj,lim,la;
  lim=0;la=0;
  p[0][0]=0;
  for(k=1;k<=n;k++)
  {
    la=lim;
    lim=min(t/a[k]+lim,l);
    for(i=0;i<=lim;i++)
    {
      bj=0;
      for(j=0;j<=t/a[k]&&j<=i;j++)
	if(i-j<=la) if(bj<(p[k-1][i-j]+(t-j*a[k])/b[k]))
		 {
		   bj=p[k-1][i-j]+(t-j*a[k])/b[k];
		   pj=j;
		 }
	p[k][i]=bj;wf[k][i]=pj;
    }
  }
  if(p[n][l]>=l) return 1;
  return 0;
}
void rec(int i,int j)
{
  if(i>0)
  {
    rec(i-1,j-wf[i][j]);
    fprintf(fout,"%d%c%d%c",wf[i][j],' ',p[i][j]-p[i-1][j-wf[i][j]],'\n');
  }
}
void cb(int tmin ,int tmax)
{
  int mij=(tmin+tmax)/2;
  if(tmin==tmax)
  {
    posibil(tmin);
    fprintf(fout,"%d%c",tmin,'\n');
    rec(n,l);
  }
  else if(posibil(mij))
	 cb(tmin,mij);
       else
	 cb(mij+1,tmax);
}
int main()
{
  int i;
  fscanf(fin,"%d%d",&n,&l);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d%d",&a[i],&b[i]);
  fclose(fin);
  cb(1,10000);
  fclose(fout);
  return 0;
}