Cod sursa(job #483235)

Utilizator cosmyoPaunel Cosmin cosmyo Data 7 septembrie 2010 16:01:49
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.84 kb
#include<cstdlib>
#include<fstream.h>
#define NMAX 50005
long k,a[NMAX],c,w[NMAX],r[NMAX],n,m;
long  long s,su;
char sol[NMAX];
void cit()
{ifstream fin("semne.in");
  fin>>k>>s;
	  for(long i=1;i<=k;++i)
		  fin>>a[i];
  fin.close();
}
int main()
{cit();
 long long i;
 ofstream fout("semne.out");
  su=0;
 long long x;
  for(i=1;i<=k;++i)
	 {x=rand()%2;
       if(x)
	    su+=a[i],w[++n]=i;
	     else 
		su-=a[i],r[++m]=i;
	 }
  do
  {if(su==s)
	   break;
	if(su>s)
	  {x=rand()%n+1;
	   su-=2*a[w[x]];
	   r[++m]=w[x];
	   w[x]=w[n--];
	  }
	  else
	if(su<s)
		{x=rand()%m+1;
	     su+=2*a[r[x]];
		 w[++n]=r[x];
         r[x]=r[m--];
		}
  }while(1);
  for(i=1;i<=n;++i)
	  sol[w[i]]=1;
  for(i=1;i<=k;++i)
	  if(sol[i])
		  fout<<'+';
	  else
		  fout<<'-';
	  fout<<'\n';
 fout.close();
 return 0;
}