Pagini recente » Cod sursa (job #156719) | Monitorul de evaluare | Cod sursa (job #1982284) | Cod sursa (job #973847) | Cod sursa (job #53464)
Cod sursa(job #53464)
#include <cstdio>
#define infile "semne.in"
#define outfile "semne.out"
#define NMAX 50003
#define HASH_MAX 10007
#define config(i,j) ((long long)((j)<<16) | (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);
}
void insert_hash(long long x)
{
NOD *a=new NOD;
a->x=x;
a->adr=hash[x%HASH_MAX];
hash[x%HASH_MAX]=a;
}
int find_hash(long long x)
{
NOD *b=hash[x%HASH_MAX];
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;
}