Cod sursa(job #59617)

Utilizator cos_minBondane Cosmin cos_min Data 9 mai 2007 21:07:44
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;

#define in "semne.in"
#define out "semne.out"
#define dim 50001

int A[dim], N, S, K[dim];
int Sel[dim];

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    K[0] = 0;
    
    scanf("%d%d", &N, &S);
    for ( int i = 1; i <= N; i++ )
        scanf("%d", &A[i]), K[i] = A[i] + K[i-1];
        
    if ( K[N] == S ) 
    {
       for ( int i = 1; i <= N; i++ )
           printf("+");
           
           return 0;
    }
    
    if ( (-1)*K[N] == -S )
    {
         for ( int i = 1; i <= N; i++ )
           printf("-");
           
           return 0;
    }
    
    int Sp = 0;
    bool ok = 1;
    int t = 0;
    int Total = K[N];
    int p, i;
    
    while ( ok == 1 )
    {
          t += 1;
          i = 1;
          Total = K[N];
          
          while ( i <= N ) 
          {
                p = rand()%N;
                if( Sel[p] != t )
                {
                    Sel[p] = t;
                    Total -= A[p];
                    if ( Total == S ) i = N+1;
                    if ( Total < S ) i = N+1;
                }
          }
          
          if ( Total == S )
          {
                for ( int i = 1; i <= N; i++ )
                   if ( Sel[i] == t ) printf("-");
                   else               printf("+");
               
               ok = 0;
          }
          
    }
}