Pagini recente » Cod sursa (job #2642228) | Cod sursa (job #115652) | Cod sursa (job #2033342) | Cod sursa (job #1228080) | Cod sursa (job #50901)
Cod sursa(job #50901)
#include <stdio.h>
#include <time.h>
#define Nmax 50002
#define MOD 1236667891
#define key 1236661
int a[Nmax], b[Nmax], v[Nmax];
int r, p;
char s[Nmax];
void srand(int seed)
{
r = 1+seed;
}
int rand()
{
r+=key;
if(r>MOD)
r -= MOD;
return r;
}
int main()
{
freopen("semne.in","r",stdin);
freopen("semne.out","w",stdout);
int i,n,S=0, A=0,B=0;
srand((int)time(0));
scanf("%d%d", &n,&S);
for(i=1;i<=n;++i)
{
scanf("%d", v+i);
if(A - B <= S)
{
a[++a[0]] = i;
A += v[i];
s[i] = '+';
}
else
{
b[++b[0]] = i;
B += v[i];
s[i] = '-';
}
}
while(A-B != S)
{
if(A-B > S)
{
// mut din A in B
int tmp = (rand()%a[0])+1;
b[++b[0]] = a[tmp];
A -= v[a[tmp]];
B += v[a[tmp]];
s[a[tmp]] = '-';
a[tmp] = a[a[0]--];
}
if(A-B < S)
{
// mut din B in A
int tmp = (rand()%b[0])+1;
a[++a[0]] = b[tmp];
A += v[b[tmp]];
B -= v[b[tmp]];
s[b[tmp]] = '+';
b[tmp] = b[b[0]--];
}
if(b[0] == 0 && A-B != S)
{
// mut din A in B
int tmp = (rand()%a[0])+1;
b[++b[0]] = a[tmp];
A -= v[a[tmp]];
B += v[a[tmp]];
s[a[tmp]] = '-';
a[tmp] = a[a[0]--];
}
if(a[0] == 0 && A-B != S)
{
// mut din B in A
int tmp = (rand()%b[0])+1;
a[++a[0]] = b[tmp];
A += v[b[tmp]];
B -= v[b[tmp]];
s[b[tmp]] = '+';
b[tmp] = b[b[0]--];
}
}
for(i=1;i<=n;++i)
printf("%c", s[i]);
return 0;
}