Cod sursa(job #731176)

Utilizator mihai995mihai995 mihai995 Data 7 aprilie 2012 17:21:23
Problema Semne Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N=50005;
int v[N],a[N],b[N],n,S;
char semn[N];

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

inline void change(char &a)
{
    if (a=='+')
        a='-';
    else
        a='+';
}

void edit(int a[],int b[])
{
    int p=rand()%a[0]+1;
    S+=2*v[a[p]];
    v[a[p]]*=-1;
    b[++b[0]]=p;
    change(semn[a[p]]);
    a[p]=a[a[0]--];

}

int main()
{
    in>>n>>S;
    srand(time(NULL));
    for (int i=1;i<=n;i++)
    {
        in>>v[i];
        S-=v[i];
        a[++a[0]]=i;
        semn[i]='+';
    }
    while (S)
        if (S>0)
            edit(b,a);
        else
            edit(a,b);
    out<<semn+1<<"\n";
    return 0;
}