Cod sursa(job #771343)

Utilizator ion824Ion Ureche ion824 Data 25 iulie 2012 17:28:31
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#include<cstdlib>
#include<ctime>
using namespace std;
int a[50005],p[50005],m[50005];
char sol[50005];

int main(void)
{
    ifstream fin("semne.in");
    ofstream fout("semne.out");
    int N,i,rd,np=0,nm=0; long long S,sc=0;
    srand(time(NULL));
    fin>>N>>S;
    for(i=1;i<=N;++i)
    { 
     fin>>a[i]; 
     rd=rand()%2;
     if(rd)
      {
       p[++np]=i;
       sc+=a[i];      
       sol[i]='+';
      }
     else
      {
      m[++nm]=i;
      sc-=a[i];
      sol[i]='-';    
      }
    }

   while(sc!=S)
   {
    if(sc<S)
     {
      rd=rand()%nm+1;
      p[++np]=m[rd];
      m[rd]=m[nm--];
      sc+=2*a[p[np]];
      sol[p[np]]='+';
            
     }  
    else
     {
      rd=rand()%np+1;
      m[++nm]=p[rd];
      p[rd]=p[np--];
      sc-=2*a[m[nm]]; 
      sol[m[nm]]='-';    
     }             
   }    
   for(i=1;i<=N;++i)fout<<sol[i];
   return 0;
}