Cod sursa(job #890584)

Utilizator crushackPopescu Silviu crushack Data 25 februarie 2013 10:36:31
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define NMax 50010
using namespace std;

typedef long long ll;
const char IN[]="semne.in",OUT[]="semne.out";

int N,solved; ll S;
int v[NMax],sol[NMax];

void randomize(){
	for (int i=1;i<=N;++i) sol[i]=rand()%2;
}

int main()
{
	int i,j;ll sum,s;
	srand(time(NULL));
	freopen(IN,"r",stdin);
	scanf("%d%lld",&N,&S);
	for (i=1;i<=N;++i) scanf("%d",v+i);
	fclose(stdin);

	while (!solved)
	{
		sum=0;
		randomize();

		for (i=1;i<=N;++i)
			sum+= sol[i] ? v[i] : -v[i];
		if (sum==S) break;

		for (i=N;i>0;--i){
			if (sol[i]){
				s=sum-v[i]-v[i];
			}
			else{
				s=sum+v[i]+v[i];
			}
			if (abs(s-S)<abs(sum-S))
			{
				sol[i]^=1;
				sum=s;
			}
		}

		if (sum==S) solved=true;
	}

	freopen(OUT,"w",stdout);
	for (i=1;i<=N;++i) printf("%c",sol[i] ? '+' : '-');
	fclose(stdout);

	return 0;
}