Pagini recente » Cod sursa (job #887703) | Cod sursa (job #316653) | Cod sursa (job #2900140) | Cod sursa (job #1705122) | Cod sursa (job #2792401)
#include <fstream>
#include <vector>
#include <string>
#include <ctime>
std::ifstream fin ("semne.in");
std::ofstream fout ("semne.out");
std::vector <int> v;
std::vector <int> knapsack[2];
int sum[2], count[2];
// 0 - plus
// 1 - minus
std::string ans;
int get_rand (int sir) {
return (rand() % count[sir]);
}
int main() {
int n, s;
fin >> n >> s;
for (int i = 1; i <= n; i++) {
int x;
fin >> x;
v.push_back(x);
}
for (int i = 0; i < n; i++) {
if (sum[0] < sum[1] + s) {
knapsack[0].push_back(i);
sum[0] += v[i];
count[0]++;
} else {
knapsack[1].push_back(i);
sum[1] += v[i];
count[1]++;
}
}
srand(time(0));
while (sum[0] != sum[1] + s) {
if (sum[0] < sum[1] + s) {
int aux = get_rand(1);
knapsack[0].push_back(knapsack[1][aux]);
sum[0] += v[knapsack[1][aux]];
count[0]++;
sum[1] -= v[knapsack[1][aux]];
knapsack[1][aux] = knapsack[1][count[1] - 1];
count[1]--;
knapsack[1].pop_back();
} else {
int aux = get_rand(0);
knapsack[1].push_back(knapsack[0][aux]);
sum[1] += v[knapsack[0][aux]];
count[1]++;
sum[0] -= v[knapsack[0][aux]];
knapsack[0][aux] = knapsack[0][count[0] - 1];
count[0]--;
knapsack[0].pop_back();
}
}
ans.resize (n, '-');
for (int i = 0; i < count[0]; i++)
ans[knapsack[0][i]] = '+';
fout << ans;
return 0;
}