Cod sursa(job #960615)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 20:17:53
Problema Semne Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.13 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;
 
 
}