Cod sursa(job #1051817)

Utilizator ELHoriaHoria Cretescu ELHoria Data 10 decembrie 2013 16:54:51
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <cstring>
#include <ctime>
#include <cstdlib>

using namespace std;

const int nmax = 50002;
int n;
int a[nmax];
bool sg[nmax];
long long S;

void go(long long sum) {
	if (sum == S) {
		return;
	}

	int pos = rand() % n;

	if (sum < S) {
		if (sg[pos]) {
			sum += 2 * a[pos];
			sg[pos] = false;
		} 
	} else {
		if (!sg[pos]) {
			sum -= 2 * a[pos];
			sg[pos] = true;
		}
	}

	go(sum);
}

int main()
{
	ifstream cin("semne.in");
	ofstream cout("semne.out");
	ios :: sync_with_stdio(false);
	cin >> n >> S;
	srand(static_cast<unsigned int>(time(0)));
	long long sum = 0;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (sum < S) {
			sum += a[i];
		} else {
			sum -= a[i];
			sg[i] = true;
		}
	}

	go (sum);

	sum = 0;
	for (int i = 0;i < n;i++) {
		cout << (sg[i] ? '-' : '+');
	}
	return 0;
}