Cod sursa(job #785639)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 9 septembrie 2012 14:50:33
Problema Semne Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

int v[50005];
bool semn[50005];
vector<int> plus,minus;

void scoate(int &poz,vector<int> &v)
{
	for(unsigned int i=poz+1;i<v.size();i++)
		swap(v[i],v[i-1]);
	v.pop_back();
}

int main()
{
	srand( time(NULL));
	long long Sp=0,Sm=0;
	int n,s;
	freopen("semne.in","r", stdin);
	freopen("semne.out","w",stdout);
	
	scanf("%d %d",&n,&s);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		if(i%2==0)
		{	
			semn[i]=0;// +
			Sp+=v[i];
			plus.push_back(i);
		}
		else
		{
			semn[i]=1; // -
			Sm+=v[i];
			minus.push_back(i);
		}
	}
	//cout<<Sp<<" "<<Sm<<endl;
	int sumatotala=Sp-Sm;
	int sumainv=Sm-Sp;
	while(sumatotala!=s && sumainv!=s)
	{
		if(sumatotala<s)
		{
			int x=rand()%minus.size();
			
			semn[minus[x]]=0;
			Sm-=v[minus[x]];
			Sp+=v[minus[x]];
			plus.push_back(minus[x]);
			scoate(x,minus);
		}
		else
		{
			int x=rand()%plus.size();
			
			semn[plus[x]]=1;
			Sm+=v[plus[x]];
			Sp-=v[plus[x]];
			minus.push_back(plus[x]);
			scoate(x,plus);
		}			
			
		sumatotala=Sp-Sm;
		sumainv=Sm-Sp;
	}
	
	if(sumatotala==s)
		for(int i=1;i<=n;i++)
			if(semn[i]==0)
				printf("+");
			else
				printf("-");
	else
		for(int i=1;i<=n;i++)
			if(semn[i]==1)
				printf("+");
			else
				printf("-");
	return 0;
}