Pagini recente » Cod sursa (job #2300615) | Cod sursa (job #1572725) | Cod sursa (job #583807) | Cod sursa (job #606302) | Cod sursa (job #284031)
Cod sursa(job #284031)
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# define MAXN 50000
long int n,a[MAXN+1],poz[MAXN+1],pozlen,neg[MAXN+1],neglen;
char semn[MAXN+1];
long long int s;
char sign[2]={'-','+'};
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);
}
int main()
{
long int ok,index,seed=time(NULL),i;
long long int suma=0;
srand(seed);
citire();
for (i=1;i<=n;i++)
{
if (suma<s) semn[i]=1;
else semn[i]=0;
if (semn[i]) {poz[++pozlen]=i;suma+=a[i];}
else {neg[++neglen]=i;suma-=a[i];}
}
for (;;)
{
while (suma<s && neglen)
{
index=(rand()%neglen)+1;
suma+=2*a[neg[index]];
semn[neg[index]]^=1;
poz[++pozlen]=neg[index];
neg[index]=neg[neglen];
neglen--;
}
if (s==suma) {scrie();return 0;}
while (suma>s && pozlen)
{
index=(rand()%pozlen)+1;
suma-=2*a[poz[index]];
semn[poz[index]]^=1;
neg[++neglen]=poz[index];
poz[index]=poz[pozlen];
pozlen--;
}
//printf(" %ld %ld \n",suma,s);
if (s==suma) {scrie();return 0;}
}
return 0;
}