Cod sursa(job #785714)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 9 septembrie 2012 18:42:28
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <string>
using namespace std;

int v[50005];
bool semn[50005];
int minusuri[50005],plusuri[50005];
string st;

int main()
{
	int minus=0,plus=0;
	srand( time(NULL));
	long long Sp=0,Sm=0,s;
	int n;
	ifstream f;
	ofstream g;
	f.open("semne.in");
	g.open("semne.out");
	
	f>>n>>s;
	getline(f,st);
	int i=0;
	
	getline(f,st);
	for(unsigned int j=0;j<st.size();j++)
	{
		if(isdigit(st[j]))
		{
			int nr=0;
			while(isdigit(st[j]))
			{
				nr=nr*10+st[j]-'0';
				j++;
			}
			v[++i]=nr;
			if(i%2==0)
			{	
				semn[i]=0;// +
				Sp+=nr;
				plusuri[++plus]=i;
			}
			else
			{
				semn[i]=1; // -
				Sm+=nr;
				minusuri[++minus]=i;
			}
		}
	}

	long long sumatotala=Sp-Sm;
	long long sumainv=Sm-Sp;
	while(sumatotala!=s && sumainv!=s)
	{
		if(sumatotala<s)
		{
			int x=rand()%minus;
			if(minus==1)
				x=1;
			else
				while(x==0)
					x=rand()%minus;
			
			semn[minusuri[x]]=0;
			Sm-=v[minusuri[x]];
			Sp+=v[minusuri[x]];
			plusuri[++plus]=minusuri[x];
			swap(minusuri[x],minusuri[minus]);
			--minus;
		}
		else
		{
			int x=rand()%plus;
			if(plus==1)
				x=1;
			else
				while(x==0)
					x=rand()%plus;
				
			semn[plusuri[x]]=1;
			Sm+=v[plusuri[x]];
			Sp-=v[plusuri[x]];
			minusuri[++minus]=plusuri[x];
			swap(plusuri[x],plusuri[plus]);
			--plus;	
		}			
			
		sumatotala=Sp-Sm;
		sumainv=Sm-Sp;
	}
	
	if(sumatotala==s)
	for(int i=1;i<=n;i++)
		g<<(semn[i]==0? "+" : "-" );
	else
		for(int i=1;i<=n;i++)
			g<<(semn[i]==0? "-" : "+");
	return 0;
}