Cod sursa(job #1417732)

Utilizator Toast97Calin Farcas Toast97 Data 10 aprilie 2015 21:33:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cstdlib>
#include <time.h>

using namespace std;

ifstream f ("semne.in");
ofstream g ("semne.out");

struct numar
{
    int indice;
    long long valoare;
} pozit[50005], negat[50005];

char sol[50005];

int main()
{
    srand (time (0));

    long long n, s, curent = 0, poz, nminus = 0, nplus = 0, nr;

    f >> n >> s;
    sol[n] = '\0';

    for (int i = 1; i <= n; i ++)
    {
        f >> nr;

        ++ nplus;

        pozit[nplus].valoare = nr;
        pozit[nplus].indice = i - 1;
        sol[i - 1] = '+';

        curent += nr;
    }

    while (curent != s)
    {
        if (curent > s)
        {
            poz = rand () % nplus + 1;

            negat[++ nminus] = pozit[poz];
            curent -= 2 * pozit[poz].valoare;
            sol[pozit[poz].indice] = '-';

            pozit[poz] = pozit[nplus];
            -- nplus;
        }
        else
        {
            poz = rand () % nminus + 1;

            pozit[++ nplus] = negat[poz];
            curent += 2 * negat[poz].valoare;
            sol[negat[poz].indice] = '+';

            negat[poz] = negat[nminus];
            -- nminus;
        }
    }

    g << sol;

    f.close ();
    g.close ();
    return 0;
}