Pagini recente » Cod sursa (job #1187921) | Cod sursa (job #1245206) | Cod sursa (job #712348) | Cod sursa (job #1726091) | Cod sursa (job #49820)
Cod sursa(job #49820)
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define maxn 50001
using namespace std;
int a[maxn], b[maxn];
int x[maxn];
int n, S;
void afis()
{
char sol[maxn];
for(int i=1;i<=a[0];i++) sol[a[i]]='+';
for(int i=1;i<=b[0];i++) sol[b[i]]='-';
freopen("semne.out", "w", stdout);
for(int i=1;i<=n;i++) printf("%c", sol[i]);
printf("\n");
exit(0);
}
int sgn(int a)
{
if(a<0) return -a;
return a;
}
void solve()
{
int i, j;
for(i=1;i<=n;i++) if((rand()*rand())&1) a[++a[0]]=i;else b[++b[0]]=i;
int sum=0;
for(i=1;i<=a[0];i++) sum+=x[a[i]];
for(i=1;i<=b[0];i++) sum-=x[b[i]];
if(sum==S) afis();
// printf("%d\n", sum);
int nr=0;
int ok;
while(1)
{
nr++;
int p1;
ok=0;
if(a[0])
{
p1=(rand()%a[0])+1;
if(sgn(S-sum) > sgn(S-(sum-(x[a[p1]])<<1)))
{
sum-=x[a[p1]]<<1;
b[0]++;
b[b[0]]=a[p1];
a[p1]=a[a[0]];
a[0]--;
ok=1;
}
}
if(b[0])
{
p1=(rand()%b[0])+1;
if(sgn(S-sum)> sgn(S-(sum+(x[b[p1]]<<1))))
{
sum+=x[b[p1]]<<1;
a[0]++;
a[a[0]]=b[p1];
b[p1]=b[b[0]];
b[0]--;
ok=1;
}
}
if(!ok)
{
if(a[0]>=b[0])
{
p1=(rand()%a[0])+1;
sum-=x[a[p1]]<<1;
b[0]++;
b[b[0]]=a[p1];
a[p1]=a[a[0]];
a[0]--;
ok=1;
}
//if(b[0]>a[0])
else
{
p1=(rand()%b[0])+1;
sum+=x[b[p1]]<<1;
a[0]++;
a[a[0]]=b[p1];
b[p1]=b[b[0]];
b[0]--;
ok=1;
}
}
//printf("%d\n", sum);
//if(nr>10){ afis();exit(0);}
if(sum==S) afis();
}
}
int main()
{
time_t s;
time(&s);
//srand(s%666013);
srand(time(0)+666);
freopen("semne.in", "r",stdin);
scanf("%d %d\n", &n, &S);
for(int i=1;i<=n;i++) scanf("%d ", x+i);
solve();
}