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