Cod sursa(job #801881)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 25 octombrie 2012 12:38:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.88 kb
#include<fstream>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
int n,v[50100];
long long S,sum;
int Plus[50100],nrp,Minus[50100],nrm,semn[50100];

int main()
{
	int i,poz;
	ifstream fin("semne.in");
	fin>>n>>S;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		Plus[++nrp]=i;
		semn[i]=1;
		sum+=(long long)v[i];
	}
	fin.close();
	
	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--;
		}
	}
	
	ofstream fout("semne.out");
	for(i=1;i<=n;i++)
	{
		if(semn[i]==1)
			fout<<"+";
		else
			fout<<"-";
	}
	fout<<"\n";
	fout.close();
	return 0;
}