Cod sursa(job #320624)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 5 iunie 2009 11:41:15
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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;        
}