Cod sursa(job #348138)

Utilizator VmanDuta Vlad Vman Data 14 septembrie 2009 15:11:30
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define Nmax 50005

int N, S, P, T, i, j, k;
int A[Nmax];
char W[Nmax];

int main()
{
 srand(time(0));
 freopen("semne.in","r",stdin);
 freopen("semne.out","w",stdout);
 
 scanf("%d %d",&N, &S);
 for (i=1; i<=N; ++i)
     scanf("%d",&A[i]), T+=A[i];
 
 for (i=1; i<=(N>>1); ++i)
     P+=A[i], W[i]=1;
 
 while ((P<<1)-T != S)
       {
        if ((P<<1)-T < S)
           {
            j = k = rand()%N+1;
            while (W[j] && j<=N) ++j;
            if (j>N) { j=k; while (W[j]) --j; }
            P+=A[j];
            W[j]=1;
           }
           else
           {
            j = k = rand()%N+1;
            while (! W[j] && j<=N) ++j;
            if (j>N) { j=k; while (! W[j]) --j; }
            P-=A[j];
            W[j]=0;
           }
       }
 
 for (i=1; i<=N; ++i)
     printf( "%c", W[i] ? '+' : '-' );
 fclose(stdout);
 
 return 0;
}