Cod sursa(job #182358)

Utilizator pinkutzaRodykutz pinkutza Data 20 aprilie 2008 19:12:18
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream.h>
int s;
int luat[44101],luatn[44101];
int rec[44101],recn[44101];
int main()
{
 int i,j,m,n,val;
 ofstream fout("diamant.out");
 ifstream fin("diamant.in");
 fin>>n>>m>>val;
 fin.close();
 int max;
 /*for(i=1;i<21;i++)
  for(j=1;j<21;j++)
   s+=i*j;
  fout<<s<<" ";44100 */
 int x[1000],dx=0;
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
   {
     dx++;
     x[dx]=i*j;
   }
 int min;
 max=0;min=0;
 luat[0]=1;
 for(i=1;i<=dx;i++)
 {
  if(-min>max)
   max=-min;
  for(j=max;j>=0;j--)
  {
   if(luat[j]>0)
    {
     luat[j+x[i]]+=luat[j];
     rec[j+x[i]]=1;
     if(j+x[i]>max)
      max=j+x[i];
    }

   if(luatn[j]==1)
    {
      if(-j+x[i]>=0)
       {
        luat[-j+x[i]]+=luatn[j];
        if(max<-j+x[i])
         max=-j+x[i];
        rec[-j+x[i]]=1;
        if(-j+x[i]>max)
         max=-j+x[i];
       }
        else
         if(-j+x[i]<0)
         {
           luatn[j-x[i]]+=luatn[j];
           recn[j-x[i]]=1;
           if(-j+x[i]<min)
            min=-j+x[i];
         }
           
    }
  }

  for(j=max;j>=0;j--)
  {
   if(luat[j]==1&&rec[j]==0)
   {
     if(j-x[i]>=0)
      luat[j-x[i]]+=luat[j];
       else
       {
        luatn[x[i]-j]+=luat[j];
        if(j-x[i]<min)
         min=j-x[i];
       }
   }
     else
       rec[j]=0;

    if(luatn[j]==1&&recn[j]==0)
    {
     luatn[j+x[i]]+=luatn[j];
     if(-j-x[i]<min)
      min=-j-x[i];
    }
      else
       recn[j]=0;

  }

}

 fout<<luat[val]<<'\n';
    

   
 fout.close();

 return 0;

}