Cod sursa(job #122903)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 13 ianuarie 2008 21:39:23
Problema Bile2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
//bile2
#include<stdio.h>
#define max(a,b)((a)>(b)?(a):(b))
FILE*fin=fopen("bile2.in","r");
FILE*fout=fopen("bile2.out","w");
int main()
{
  unsigned int n,d,a,b,i,g=0,o=0,nw=1,aux,j,k;
  unsigned long long cp[1001][1001],cf[2][1001],sum;
  fscanf(fin,"%d" "%d" "%d" "%d",&n,&d,&a,&b);
  cp[1][0]=0;cp[1][1]=1;cp[0][1]=0;cp[0][0]=0;
  for(i=2;i<=n;i++)
    for(j=1;j<i;j++)
    {
      cp[i][j]=cp[i-1][j]+cp[i-1][j-1];
      cp[i][i]=1;
      cp[i][0]=0;
    }
  for(i=0;i<=n;i++)
    cf[0][i]=0;
  for(j=2;j<=n;j++,aux=o,o=nw,nw=aux)
  {
    for(i=j;i<=n;i++)
    {
      cf[nw][i]=0;
      for(k=j-1;k<i-d;k++)
	cf[nw][i]+=cf[o][k];
      for(k=max(i-d,j-1);k<i;k++)
	cf[nw][i]+=cp[k-1][j-1];
      if(cf[nw][i]*b>=cp[n][j]*a){g=1;fprintf(fout,"%d",j);break;}
    }
    if(g==1) break;
  }
  fclose(fin);
  fclose(fout);
  return 0;
}