Cod sursa(job #984914)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 15 august 2013 18:52:55
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int NMAX = 50005;
int i,N,P,M,Poz;
int A[NMAX],Plus[NMAX],Minus[NMAX];
long long S,Sum;
char Sign[NMAX];
int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    srand(time(NULL));
    scanf("%d%lld",&N,&S);
    for(i=1;i<=N;i++)
    {
        scanf("%d",&A[i]);
        if(Sum<S)
        {
            Sum+=A[i];
            Sign[i]='+';
            Plus[++P]=i;
        }
        else
        {
            Sum-=A[i];
            Sign[i]='-';
            Minus[++M]=i;
        }
    }
    while(Sum!=S)
    {
        if(Sum<S)
        {
            Poz=rand()%M+1;
            Sign[Minus[Poz]]='+';
            Sum+=2*A[Minus[Poz]];
            Plus[++P]=Minus[Poz];
            Minus[Poz]=Minus[M--];
        }
        else
        {
            Poz=rand()%P+1;
            Sign[Plus[Poz]]='-';
            Sum-=2*A[Plus[Poz]];
            Minus[++M]=Plus[Poz];
            Plus[Poz]=Plus[P--];
        }
    }
    for(i=1;i<=N;i++) printf("%c",Sign[i]);
    return 0;
}