Cod sursa(job #71422)

Utilizator floringh06Florin Ghesu floringh06 Data 10 iulie 2007 14:41:18
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
using namespace std;

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

  #define ll long long
  #define MAX_N 50005
  #define MAX_V 5000005

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

void inc()
{
  int i = 1;
  while (sc < S && i <= n)
    {
      if (stat[i]==false)
       {
         stat[i] = true;
         sc += a[i]<<1;
       }
      ++ i;
    }
}

void dec ()
{
  int i = n;
  while (sc > S && i >= 0)
    {
      if (stat[i]==true)
       {
         stat[i] = false;
         sc -= a[i]<<1;
       }
      -- i;
    }
}

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<=600; i++)
       {
         if (sc<S) inc();
         if (sc>S) dec();
         if (sc==S) break;
       }  
       
     for (i=1; i<=n; i++)
      if (stat[i]==true) printf("+");
       else printf("-");     
          
     fclose(stdin); 
     fclose(stdout);
     
     return 0;
}