Pagini recente » Cod sursa (job #76199) | Cod sursa (job #3191216) | Cod sursa (job #2978496) | Cod sursa (job #1563861) | Cod sursa (job #2787394)
#include <bits/stdc++.h>
using namespace std;
/**
Algoritmi randomizati
NP-complete
*/
ifstream fin ("semne.in");
ofstream fout ("semne.out");
int n, a[50005];
long long s;
int P[50005], np , M[50005], nm;
int main()
{
long long suma;
fin >> n >> s;
for (int i = 1; i <= n; i++)
fin >> a[i];
srand (time (0));
suma = 0;
for (int i = n; i > 0; i--)
if (suma < s)
{
suma += a[i];
P[np++] = i;
}
else
{
suma -= a[i];
M[nm++] = i;
}
while (suma != s)
{
if (suma < s)
{
int j = rand () % nm;
suma = suma + 2 * a[M[j]];
P[np++] = M[j];
M[j] = M[nm - 1];
nm--;
}
else
{
int j = rand() % np;
suma = suma - 2 * a[P[j]];
M[nm++] = P[j];
P[j] = P[np -1];
np--;
}
}
char sol[50002];
for (int i = 1; i <= n; i++)
sol[i] = '+';
for (int i = 0; i < nm; i++)
sol[M[i]] = '-';
fout << (sol + 1) << "\n";
fout.close();
return 0;
}