Cod sursa(job #204474)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 24 august 2008 14:55:50
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#define bulan maxim :)

#include <cstdio>
#include <cstdlib>
#include <ctime>

#define IN "semne.in"
#define OUT "semne.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<17

int sum,N,S;
int V[N_MAX];
int minus[N_MAX],plus[N_MAX];
char sol[N_MAX];

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d",&N,&S);
	FOR(i,1,N)
	{
		scanf("%d", &V[i]);
		if(sum + V[i] <= S)
			sum += V[i],
			plus[ ++plus[0] ] = i,
			sol[i] = '+';
		else
			sum -= V[i],
			minus[ ++minus[0] ] = i,
			sol[i] = '-';
	}		
}

void solve()
{
	int x;
	srand(time(0));
	while(sum != S)
	{
		if(sum < S)
		{
			x = rand() % minus[0] + 1;
			sum += V[ minus[x] ]<<1;
			plus[ ++plus[0] ] = minus[x];
			sol[ minus[x] ] = '+';
			minus[ x ] = minus[ minus[0]-- ];
		}
		else
		{
			x = rand() % plus[0] + 1;
			sum -= V[ plus[x] ]<<1;
			minus[ ++minus[0] ] = plus[x];
			sol[ plus[x] ] = '-';
			plus[x] = plus[ plus[0]-- ];
		}
	}	
	FOR(i,1,N)
		printf("%c",sol[i]);
	printf("\n");	
}

int main()
{
	scan();
	solve();
	return 0;
}