Cod sursa(job #920614)

Utilizator superman_01Avramescu Cristian superman_01 Data 20 martie 2013 15:59:00
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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,nrp,nrm,n;
long long sum,S;

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

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

    {
        fscanf(f,"%d",&v[i]);
        plus[++nrp]=i;
        semn[i]=1;
        sum+=(long long)v[i];
   }
   fclose(f);
   srand(time(NULL));
   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--;
      }
      else
      {
          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(g);
   return 0;


}