Pagini recente » Cod sursa (job #2960885) | Cod sursa (job #1603020) | Cod sursa (job #1188574) | Cod sursa (job #2006512) | Cod sursa (job #2792687)
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>
typedef long long ll;
std::ifstream fin ("semne.in");
std::ofstream fout ("semne.out");
int const nmax = 50000;
int v[nmax + 5];
int knapsack[2][nmax + 5];
ll sum[2];
int count[2];
// 0 - plus
// 1 - minus
std::string ans;
int main() {
int n; ll s;
fin >> n >> s;
for (int i = 1; i <= n; i++)
fin >> v[i];
for (int i = 1; i <= n; i++) {
if (sum[0] <= sum[1] + s) {
knapsack[0][++count[0]] = i;
sum[0] += v[i];
} else {
knapsack[1][++count[1]] = i;
sum[1] += v[i];
}
}
srand(time(0));
while (sum[0] != sum[1] + s) {
if (sum[0] < sum[1] + s) {
int aux = (rand() % count[1]) + 1;
knapsack[0][++count[0]] = knapsack[1][aux];
sum[0] += v[knapsack[1][aux]];
sum[1] -= v[knapsack[1][aux]];
knapsack[1][aux] = knapsack[1][count[1]--];
} else {
int aux = (rand() % count[0]) + 1;
knapsack[1][++count[1]] = knapsack[0][aux];
sum[1] += v[knapsack[0][aux]];
sum[0] -= v[knapsack[0][aux]];
knapsack[0][aux] = knapsack[0][count[0]--];
}
}
ans.resize (n, '-');
for (int i = 1; i <= count[0]; i++)
ans[knapsack[0][i] - 1] = '+';
fout << ans;
return 0;
}