Cod sursa(job #286190)

Utilizator crawlerPuni Andrei Paul crawler Data 23 martie 2009 16:15:08
Problema Semne Scor 100
Compilator cpp Status done
Runda qwerty-1 Marime 1.38 kb
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define Nmax 50100

int x[Nmax], A[Nmax], B[Nmax], n1, n2, n;
long long S1, S2, S;

char semne[Nmax];

int main()
{
     freopen("semne.in","r",stdin);
     freopen("semne.out","w",stdout);

     srand(time(0));
     
     scanf("%d%lld", &n, &S);
     
     for (int i=1;i<=n;++i)
     {
          scanf("%d", x+i);
          if (S1<S2)
               A[++n1] = i,
               S1 += x[i];
          else
               B[++n2] = i,
               S2 += x[i];          
     }
     
     int tmp, el;
     
     while (S1-S2!=S)
     {
          if (S1 - S2 > S)
          {
               el = rand()%n1 + 1;
               tmp = A[el];
               A[el] = A[n1--];
               S1 -= x[tmp];
               B[++n2] = tmp;
               S2 += x[tmp];                        
          }         
          if (S1 - S2 < S)               
          {
               el = rand()%n2 + 1;
               tmp = B[el];
               B[el] = B[n2--];
               S2 -= x[tmp];
               A[++n1] = tmp;
               S1 += x[tmp];                        
          }
     }
     
     for (int i=1;i<=n1;++i)
          semne[A[i]] = '+';
     
     for (int i=1;i<=n2;++i)
          semne[B[i]] = '-';
          
     printf("%s\n", semne+1);
               
     return 0;     
}