Cod sursa(job #427125)

Utilizator otilia_sOtilia Stretcu otilia_s Data 27 martie 2010 15:59:16
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <cstdlib>
using namespace std;
#define NMAX 50004
bool semn[NMAX];
int poz[NMAX],neg[NMAX],v[NMAX],nn,np,n;
long long S,sc;

void citire()
{
	ifstream fin("semne.in");	
	fin>>n>>S;
	sc=np=nn=0;
	int i;
	for (i=1;i<=n;++i)
	{
	 fin>>v[i];
	 if (sc<S){ sc+=v[i]; semn[i]=1; poz[++np]=i;}
	    else  { sc-=v[i]; semn[i]=0; neg[++nn]=i;}
	}
	fin.close();
}

void afisare()
{
	ofstream fout("semne.out");
	int i;
	for (i=1;i<=n;++i)
	 if (semn[i]) fout<<"+";
	    else fout<<"-";
	fout.close();
}

int main()
{
	citire();
	srand(time(0));
	
	int i;
	while (sc!=S)
	{
		if (sc<S)
		   {
			i=(rand()%nn)+1;
			sc+=2*v[neg[i]];
			poz[++np]=neg[i]; semn[neg[i]]=1;
			neg[i]=neg[nn--];			
		   }
		  else
		  {
			i=(rand()%np)+1;
			sc-=2*v[poz[i]];
			neg[++nn]=poz[i]; semn[poz[i]]=0;
			poz[i]=poz[np--];	  
		  }
	}
	
	afisare();
	return 0;
}