Cod sursa(job #34861)

Utilizator cos_minBondane Cosmin cos_min Data 21 martie 2007 16:00:03
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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

long long a[dim];
long long stotal=0, stotal2=0;
char v[dim];
int n, s;
bool sel[dim];

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    int gasit=0;
    
    scanf("%d%d",&n,&s);
    
    for ( int i = 1; i <= n; i++ ) scanf("%lld",&a[i]), stotal += a[i], v[i] = '+';
    
    a[0] = 0;
    a[n] = 0;
    
    while ( !gasit )
    {
          for (int i = 1; i <= n; i++ ) sel[i] = 0;
           
          stotal2 = stotal;
          int j;
          int t=0;
          int ok =0;
          
          while ( ok == 0 && t < n )
          {
                j = rand()%(n);
                if ( j == 0 ) continue; 
                if ( !sel[j] ) stotal2 -= a[j], sel[j] = 1, t++;
                
               // printf("%d ", j);
                
                if ( stotal2 == s ) gasit = 1, ok = 1;
                if ( stotal2 < s ) ok = 1;
          }
          
       //   printf("\n");
    }
    
    for ( int i = 0; i < n; i++ )
    {
        if ( !sel[i+1] ) v[i] = '-';
        else            v[i] = '+';
    }
    
    for ( int i = 0; i < n; i++ )
        printf("%c",v[i]);
    //printf("%d ", stotal2);
}