Cod sursa(job #71362)

Utilizator info_arrandrei gigea info_arr Data 10 iulie 2007 13:13:45
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
using namespace std;

#include <cstdio>
#include <time.h>
#include <cstdlib>

  #define ll long long
  #define MAX_N 50005

int a[MAX_N];
ll s[MAX_N],S,sc;
bool stat[MAX_N];
int n,i;

void add()
{
  int i;
  for (i=1; i<=n; i++)
   if (stat[i]==false) break;
  sc+=a[i]<<1;
  stat[i]=true;
}  
   
void sub()
{
  int i;
  for (i=1; i<=n; i++)
   if (stat[i]==true) break;
  sc-=a[i]<<1;
  stat[i]=false;
}  


int main()
{
     freopen("semne.in","r",stdin);
     freopen("semne.out","w",stdout);
   
     scanf("%d %lld",&n,&S);
     
     for (i=1; i<=n; i++) 
      scanf("%d",a+i);
     s[n]=sc=a[n];
     
     for (i=n-1; i>=1; i--)
      { 
       sc +=(long long)a[i];
       s[i]=(long long)sc;
      }  
     sc=0;
     srand(unsigned(time(NULL)));    
     int c=0,in=0;
     bool ok;
     for (i=1; i<=n; i++)
      {
         c=rand() % 2+1;
         if (sc+s[i]==S) 
          { 
            in=i; ok=true;
            break;
          }
         if (sc-s[i]==S)
          {
            in=i; ok=false;
            break;
          }                  
         if (c&1) {  stat[i]=true; sc+=a[i]; }

          else { stat[i]=false; sc-=a[i]; }
      }          
     
     if (in!=0)
      {
        if (ok==true)
           for (i=in; i<=n; i++)
            stat[i]=true;
        else 
           for (i=in; i<=n; i++) 
            stat[i]=false;
        for (i=1; i<=n; i++)
          if (stat[i]==true) printf("+");
            else printf("-");
        
        return 0;
      }
     else
      for (i=1; i<=1000; i++)     
       {
        if (sc<S) 
         add();
        if (sc>S)
         sub();
       }     
     
     for (i=1; i<=n; i++)
      if (stat[i]==true) printf("+");
       else printf("-");     
          
     fclose(stdin); 
     fclose(stdout);
     
     return 0;
}