Cod sursa(job #59628)

Utilizator cos_minBondane Cosmin cos_min Data 9 mai 2007 21:30:04
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 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;
int Sel[dim];
long long Total = 0;

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

    scanf("%d%d", &N, &S);
    for ( int i = 1; i <= N; i++ )
        scanf("%d", &A[i]), Total += A[i];
        
    if ( Total == S ) 
    {
       for ( int i = 1; i <= N; i++ )
           printf("+");
           
           return 0;
    }
    
    if ( (-1)*Total == -S )
    {
         for ( int i = 1; i <= N; i++ )
           printf("-");
           
           return 0;
    }
    
    int Sp = 0;
    bool ok = 1;
    int t = 0;
    long long Total2 = Total;
    int p, i;
    
    srand(time(0));
    
    while ( ok == 1 )
    {
          t += 1;
          i = 1;
          Total2 = Total;
          
          while ( i <= N ) 
          {
                p = rand()%N+1;

                if ( Total2 == S ) 
                {
                     i = N+1;
                     continue;
                }
                
                if( Sel[p] == t && Total2 < S )
                {
                    Sel[p] = -t;
                    Total2 += 2*A[p];
                    if ( Total2 == S ) i = N+1;
                   
                }
                else if ( Sel[p] == -t && Total2 > S )
                {
                     Sel[p] = t;
                     Total2 -= 2*A[p];
                     if ( Total2 == S ) i = N+1;
                }
                else if ( Sel[p] != t && Sel[p] != -t )
                {
                     Sel[p] = t;
                     Total2 -= 2*A[p];
                     if ( Total2 == S ) i = N+1;
                    /* if ( Total2 < S ) Total2 += 2*A[p], Sel[p] = -t;
                    
                     if ( Total2 == S ) i = N+1;*/
                    
                     i += 1;
                }
                
                //printf("%d\n", Total2 );
                
          }
          
          if ( Total2 == S )
          {
                for ( int i = 1; i <= N; i++ )
                {
                    if ( Sel[i] == t ) printf("-");
                    else               printf("+");         
                }
               
               ok = 0;
          }
          //printf("\n");
          
    }
}