Cod sursa(job #771336)

Utilizator ion824Ion Ureche ion824 Data 25 iulie 2012 17:21:17
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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(0));
    fin>>N>>S;
    for(i=1;i<=N;++i)
    { 
     fin>>a[i]; 
     if(i&1)
      {
       p[++np]=i;
       sc+=a[i];      
       sol[i]='+';
      }
     else
      {
      m[++nm]=i;
      sc-=a[i];
      sol[i]='-';    
      }
    }
   if(sc==-S)for(i=1;i<=N;++i)if(sol[i]=='-')sol[i]=='+'; else sol[i]='-';
   sc=-sc;
   while(sc!=S)
   {
    if(sc<S && nm)
     {
      rd=(rand()%nm)+1;
      sc+=2*a[m[rd]];
      sol[m[rd]]='+';
      m[rd]=m[nm--];            
     }  
    if(sc>S && np)
     {
      rd=(rand()%np)+1;
      sc-=2*a[p[rd]]; 
      sol[p[rd]]='-';
      p[rd]=p[np--];
     }             
   }    
   for(i=1;i<=N;++i)fout<<sol[i];
   return 0;
}