Cod sursa(job #683121)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 20 februarie 2012 01:09:15
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;

char ok[50002];
int no[50002];bool stop = 0;
void rez(int z, int n, string semne, long long rs, long long nr[])
{
	int i;
	long long s;
	if(stop);
	else if(z-1 == n)
	{
		
		if(ok[1] == '+')
			s = nr[1];
		else
			s = nr[1] * -1;

		for(i=2;i<=n;++i)
		{
			if(ok[i] == '+')
				s += nr[i];
			else
				s -= nr[i];
		}

		if(s == rs)
		{
			for(i=1;i<=n;++i)
				cout<<ok[i];
			cout<<"\n";
			stop = 1;
		}
	}
	else
		for(i=1;i<=n;++i)
			if(!no[i])
			{
				ok[z] = semne[i];
				
				no[i] = 1;
				
				rez(z+1, n, semne, rs, nr);
				
				no[i] = 0;
				
			}
		
}

int main()
{
	
	freopen("semne.in", "r", stdin);
	
	freopen("semne.out", "w", stdout);
	
	string semne (1, 0);
	
	int i, n;
	
	long long nr[50002], s;

	nr[0] = 0;

	scanf("%d %I64d\n", &n, &s);
	
	for(i=1;i<=n;++i)
		scanf("%I64d", &nr[i]);

	fclose(stdin);

	for(i=1;i<=n;++i)
		semne.push_back((i%2)?'+':'-');

	rez(1, n, semne, s, nr);
	
	fclose(stdout);

	return 0;

}