Cod sursa(job #920519)

Utilizator superman_01Avramescu Cristian superman_01 Data 20 martie 2013 15:36:00
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>

#define NMAX 50005

FILE *f=fopen("semne.in","r");
FILE *g=fopen("semne.out","w");

using namespace std;

int plus[NMAX],minus[NMAX],v[NMAX],semn[NMAX];
int poz,sum,S,nrp,nrm,n;

int main( void )
{
    fscanf(f,"%d%d",&n,&S);

    for(int i(1); i <= n ; ++i)

    {
        fscanf(f,"%d",&v[i]);
        sum+=v[i];
        plus[++nrp]=i;
        semn[i]=1;
   }
   while( sum != S)
   {
       if(sum > S)
       {
           poz=rand()%nrp+1;
           sum-=2*v[plus[poz]];
           semn[plus[poz]]=-1;
           minus[++nrm]=plus[poz];
           swap(plus[poz],plus[nrp]);
           --nrp;
      }
      if( sum < S)
      {
          poz=rand()%nrm+1;
          sum+=2*v[minus[poz]];
          semn[minus[poz]]=1;
          plus[++nrp]=minus[poz];
          swap(minus[poz],minus[nrm]);
          --nrm;
     }
   }

   for(int i(1); i <= n ; i++)
    if(semn[i] == 1)
    fprintf(g,"+");
   else
    fprintf(g,"-");
   fclose(f);
   fclose(g);
   return 0;


}