Cod sursa(job #1250023)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 27 octombrie 2014 19:11:15
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <set>
#include <string>
using namespace std;

typedef pair <int, int> nr;
vector <nr> pls, mns;
string semne;

int main () {
    ifstream cin("semne.in");
    ofstream cout("semne.out");

    int n;
    long long s;
    cin >> n >> s;
    long long sum = 0;

    srand(time(NULL));
    for (int i = 0 ; i < n ; ++i) {
        int a;
        cin >> a;

        int semn = rand() % 2;
        if (semn) {
            sum += a;
            pls.push_back(make_pair(a, i));
            semne += '+';
        }
        else {
            sum -= a;
            mns.push_back(make_pair(a, i));
            semne += '-';
        }
    }

    while (sum != s) {
        if (sum < s) {
            int p = rand() % mns.size();
            sum += 2 * mns[p].first;
            semne[mns[p].second] = '+';
            pls.push_back(make_pair(mns[p].first, mns[p].second));
            mns[p] = mns[mns.size() - 1];
            mns.pop_back();
        }
        else {
            int p = rand() % pls.size();
            sum -= 2 * pls[p].first;
            semne[pls[p].second] = '-';
            mns.push_back(make_pair(pls[p].first, pls[p].second));
            pls[p] = pls[pls.size() - 1];
            pls.pop_back();
        }
    }

    cout << semne;
    return 0;
}