Cod sursa(job #53475)

Utilizator stef2nStefan Istrate stef2n Data 22 aprilie 2007 11:38:28
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <cstdlib>

#define infile "semne.in"
#define outfile "semne.out"
#define NMAX 50003
#define HASH_MAX 666013
#define config(i,j) ((long long)((j)<<16) | (long long)(i))
struct NOD{long long x; NOD *adr;};

FILE *fin,*fout;
int N,a[NMAX];
long long S,sum[NMAX];
NOD *hash[HASH_MAX];
char semn[NMAX];

void read_data()
  {
   fin=fopen(infile,"r");
   fscanf(fin,"%d %Ld",&N,&S);
   for(int i=1;i<=N;i++)
      {
       fscanf(fin,"%d",&a[i]);
       if(i==1)
         sum[i]=a[i];
       else
         sum[i]=sum[i-1]+a[i];
      }
   fclose(fin);
  }

inline int h(long long x)
  {
   return llabs(x)%HASH_MAX;
  }

void insert_hash(long long x)
  {
   NOD *a=new NOD;
   a->x=x;
   a->adr=hash[h(x)];
   hash[h(x)]=a;
  }

int find_hash(long long x)
  {
   NOD *b=hash[h(x)];
   while(b)
        {
         if(b->x==x)
           return 1;
         b=b->adr;
        }
   return 0;
  }

bool solve(unsigned int n, long long s)
  {
   if(!n)
     if(!s)
       return 1;
     else
       return 0;
   if(s<-sum[n] || s>sum[n])
     return 0;
   if(find_hash(config(n,s)))
     return 1;
   if(solve(n-1,s+a[n]) || solve(n-1,s-a[n]))
     {
      insert_hash(config(n,s));
      return 1;
     }
   return 0;
  }

void reconstituie(unsigned int n, long long s)
  {
   if(!n)
     return;
   if(find_hash(config(n-1,s+a[n])))
     {
      semn[n]='-';
      reconstituie(n-1,s+a[n]);
     }
   else
     {
      semn[n]='+';
      reconstituie(n-1,s-a[n]);
     }
  }


int main()
{
read_data();
for(int i=0;i<HASH_MAX;i++)
   hash[i]=NULL;
insert_hash(config(0,0));
solve(N,S);
reconstituie(N,S);
fout=fopen(outfile,"w");
for(int i=1;i<=N;i++)
   fprintf(fout,"%c",semn[i]);
fprintf(fout,"\n");
fclose(fout);
return 0;
}