Pagini recente » Cod sursa (job #271909) | Cod sursa (job #2104499) | Cod sursa (job #1844324) | Cod sursa (job #2030929) | Cod sursa (job #281247)
Cod sursa(job #281247)
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# define MAXN 50000
long int n,a[MAXN+1];
char semn[MAXN+1];
long long int s;
char sign[2]={'-','+'};
long int mult[2]={-1,1},determinist;
const long int MAXL=(long int)1<<20;
typedef struct {long int val, tata;} NOD;
NOD v[MAXL+1];
long int len;
void citire()
{
FILE *f=fopen("semne.in","r");
fscanf(f,"%ld%lld",&n,&s);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&a[i]);
fclose(f);
}
void scrie()
{
FILE *g=fopen("semne.out","w");
long int i;
for (i=1;i<=n;i++)
fprintf(g,"%c",sign[semn[i]]);
fprintf(g,"\n");
fclose(g);
}
void gen(long int pas, long int final,long int valoare,long int tatal)
{
if (pas>final)
{
v[++len].val=valoare;
v[len].tata=tatal;
}
else
{
gen(pas+1,final,valoare-a[pas],(tatal<<1));
gen(pas+1,final,valoare+a[pas],(tatal<<1)+1);
}
}
int compara(const void *a,const void *b) {return ((NOD*)a)->val-((NOD*)b)->val;}
long int binsearch(long int li, long int lf, long int key)
{
long int m,i;
while (li<=lf)
{
m=(li+lf)/2;
if (v[m].val==key)
{
//tre' sa scrii niste semne
for (i=1;i<=determinist;i++)
{
semn[determinist-i+1]=v[m].tata&1;
v[m].tata>>=1;
}
return 1;
}
if (v[m].val<key) li=m+1;
else if (v[m].val>key) lf=m-1;
}
return 0;
}
int main()
{
long int ok,index,seed=time(NULL);
long int i;long long int suma=0;
determinist=20<n?20 : n;
//determinist=2;
srand(seed);
citire();
//genereaza_valorile_pt_primele_20
gen(1,determinist,0,0);
qsort(v,len,sizeof(NOD),compara);
for (i=determinist+1;i<=n;i++)
{
semn[i]=rand()%2;
suma+=a[i]*mult[semn[i]];
}
if (determinist>=len)
{
ok=binsearch(1,len,s);
if (ok)
{
scrie();
return 0;
}
}
else
for (i=1;i<=15000000;i++)
{
index=(rand()%(n-determinist))+determinist+1;
semn[index]^=1;
suma=suma+2*a[index]*mult[semn[index]];
ok=binsearch(1,len,s-suma);
if (ok)
{
scrie();
return 0;
}
}
return 0;
}