Pagini recente » Cod sursa (job #933364) | Cod sursa (job #2454038) | Cod sursa (job #2489262) | Cod sursa (job #760185) | Cod sursa (job #50056)
Cod sursa(job #50056)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define maxn 50001
int x[maxn], n, S;
int sgn(int a)
{
if(a<0) return -a;
return a;
}
void afis(bool a[])
{
int i;
for(i=1;i<=n;i++) if(a[i]) printf("+"); else printf("-");
printf("\n");
exit(0);
}
void solve()
{
bool a[maxn];
int i, j;
int sum=0;
for(i=1;i<=n;i++) a[i]=rand()&1;
for(i=1;i<=n;i++) if(a[i]) sum+=x[i]; else sum-=x[i];
int p, ok;
int ntimes=10;
while(1)
{
ok=0;
if(sum==S) afis(a);
p=(rand()%n)+1;
for(i=1;i<=ntimes;i++)
{
if(a[p] && ( sgn(S-(sum-2*x[p])) < sgn((S-sum))) )
{
sum-=2*x[p];
a[p]=0;
ok=1;
}
if(!a[p] && ( sgn(S-(sum+2*x[p])) < sgn((S-sum))) )
{
sum+=2*x[p];
a[p]=1;
ok=1;
}
}
if(!ok)
{
if(a[p])
{
sum-=2*x[p];
a[p]=0;
}
else
{
sum+=2*x[p];
a[p]=1;
}
}
if(sum==S) afis(a);
}
}
int main()
{
time_t s;
time(&s);
srand(s%666013);
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%d %d\n", &n, &S);
for(int i=1;i<=n;i++) scanf("%d ", x+i);
solve();
return 0;
}