Cod sursa(job #805863)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 noiembrie 2012 12:28:02
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<time.h>
#include<vector>
#include<stdlib.h>
using namespace std;
int a[50005];
vector<int> p;
vector<int> m;
char str[50005];
int main()
{
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	int s,n,i;
	scanf("%d%d",&n,&s);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	srand(time(0));
	int s1,s2,c;
	s1=0;s2=0;
	for(i=1;i<=n;i++)
	{
		c=rand()%2;
		if(c%2==0)
		{
			s1+=a[i];
			p.push_back(i);
		}
		else
		{
			s2+=a[i];
			m.push_back(i);
		}
	}
	while(s1-s2!=s)
		if(s1-s2>s)
		{
			c=rand()%p.size();
			vector<int>:: iterator it;
			it=(p.begin()+c);
			s1=s1-*it;
			s2=s2+*it;
			m.push_back(*it);
			swap(p[c],p[p.size()-1]);
			p.pop_back();
		}
		else
		{
			c=rand()%m.size();
			vector<int>:: iterator it;
			it=(m.begin()+c);
			s1=s1+*it;
			s2=s2-*it;
			p.push_back(*it);
			swap(m[c],m[m.size()-1]);
			m.pop_back();
		}
	for(i=0;i<p.size();i++)
		str[p[i]]='+';
	for(i=0;i<m.size();i++)
		str[m[i]]='-';
	puts(str+1);
	return 0;
}