Cod sursa(job #131911)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 4 februarie 2008 18:08:57
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
//lapte
#include<stdio.h>
FILE*fin=fopen("lapte.in","r");
FILE*fout=fopen("lapte.out","w");
int n,l,t,wfi[101][101],wfj[101][101],p[101][101],a[101],b[101];
int posibil(int t);
void rec(int i,int j)
{
  if(p[i][j]>0)
  {
    rec(wfi[i][j],wfj[i][j]);
    fprintf(fout,"%d%c%d%c",(i-wfi[i][j])*a[p[i][j]],' ',(j-wfj[i][j])*b[p[i][j]],'\n');
  }
}
int cb(int tmin,int tmax)
{
  int mij=(tmin+tmax)/2,i;
  if(tmin==tmax)
  {
    posibil(tmin);
    fprintf(fout,"%d%c",tmin,'\n');
    rec(l,l);
    for(i=p[l][l]+1;i<=n;i++) fprintf(fout,"0 0\n");
  }
  else if(posibil(mij))
	   return cb(tmin,mij);
       else
	   return cb(mij+1,tmax);
  return 0;
}
int posibil(int t)
{
  int i,j,k,tm,ii,jj;
  for(i=0;i<=l;i++)
    for(j=0;j<=l;j++)
      p[i][j]=-1;
  p[0][0]=0;
  for(k=1;k<=n;k++)
    for(i=0;i<=l;i++)
      for(j=0;j<=l;j++)
	if(p[i][j]!=-1&&p[i][j]<k)
	for(tm=0;tm<=t/a[k];tm++)
	{
	  ii=i+tm;
	  for(jj=0;jj<=j+(t-tm*a[k])/b[k];jj++)
	  if(p[ii][jj]==-1&&ii<=l&&jj<=l)
	  {
	    wfi[ii][jj]=i;
	    wfj[ii][jj]=j;
	    p[ii][jj]=k;
	    if(ii==l&&jj==l) return 1;
	  }
	}
  return 0;
}
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,100);
  fclose(fout);
  return 0;
}