Pagini recente » Cod sursa (job #769725) | Cod sursa (job #3128980) | Cod sursa (job #1962470) | Cod sursa (job #1644963) | Cod sursa (job #50814)
Cod sursa(job #50814)
#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()&1) a[++a[0]]=i;else b[++b[0]]=i;
int suma=0, sumb=0;
for(i=1;i<=n;i++) if(suma<=sumb) a[++a[0]]=i, suma+=x[i]; else b[++b[0]]=i, sumb+=x[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(ok)
{
nr++;
int p1;
ok=0;
if(sum<S && b[0]>0)
{
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;
if(sum==S) afis();
}
}
else if(sum>S && a[0]>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(sum==S) afis();
}
}
if(sum==S) afis();
continue;
if(sum==S) afis();
}
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();
}