Cod sursa(job #606615)

Utilizator crushackPopescu Silviu crushack Data 5 august 2011 17:08:06
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NMax 50010

const char IN[]="semne.in",OUT[]="semne.out";
const int Prim= 666013;
const int Prim2=10001;

int N;
long long S;
int a[NMax];
bool sign[NMax];

void randomize()
{
    int i;
    for (i=0;i<N;++i)
        sign[i]= rand()%2;
}

inline int abs(int x){
    return x<0 ? -x : x;
}

inline long long abs(long long x){
    return x<0 ? -x : x;
}

void solve()
{
    int i;
    long long s=0;
    srand((time(NULL)*Prim2)%Prim);

    while (s!=S)
    {
        randomize();
        for (i=0;i<N;++i) s+= (a[i]= sign[i] ? a[i] : -a[i]);
        for (i=N-1;i>=0;--i) if ( abs( S - ((-2*a[i]) + s))<abs( S - s))
            sign[i]=!sign[i],s-= 2*a[i],a[i]=-a[i];
        for (i=0;i<N;++i) a[i]=abs(a[i]);
    }
}

int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%d%lld",&N,&S);
    for (i=0;i<N;++i)
        scanf("%d",a+i);
    fclose(stdin);

    solve();

    freopen(OUT,"w",stdout);
    for (i=0;i<N;++i)
        printf("%c", sign[i] ? '+' : '-');
    printf("\n");
    fclose(stdout);

    return 0;
}