Pagini recente » Cod sursa (job #1308266) | Rating Bulgaru Robert (rrobert) | Monitorul de evaluare | Cod sursa (job #2794889) | Cod sursa (job #615079)
Cod sursa(job #615079)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#define MAXN 50010
using namespace std;
int N, S, A[MAXN], gplus[MAXN], gmin[MAXN];
char r[MAXN];
int main() {
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%d %d\n", &N, &S);
int s = 0;
for(int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
}
srand(time(NULL));
int n, m;
n = m = 0;
for(int i = 1; i <= N; i++) {
int bit = rand() % 2;
if(bit != 0) {
gplus[++n] = i;
s += A[i];
}
else {
gmin[++m] = i;
s -= A[i];
}
}
for(; ; ) {
if(s == S) break;
if(s < S) {
int x1 = rand() % m; ++x1;
gplus[++n] = gmin[x1];
swap(gmin[x1], gmin[m]);
--m;
s += 2 * A[gplus[n]];
}
else if(s > S) {
int x2 = rand() % n; ++x2;
gmin[++m] = gplus[x2];
swap(gplus[x2], gplus[n]);
--n;
s -= 2 * A[gmin[m]];
}
}
for(int i = 1; i <= n; i++)
r[gplus[i]] = '+';
for(int i = 1; i <= m; i++)
r[gmin[i]] = '-';
for(int i = 1; i <= N; i++)
printf("%c", r[i]);
return 0;
}