Cod sursa(job #395376)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 12 februarie 2010 22:17:02
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define NMAX 50010

int N, V[NMAX], poz[NMAX], neg[NMAX], A[NMAX];
long long S;

int main()
{
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	scanf("%d %lld",&N,&S);
	srand (time (NULL));
	int i;
	long long s=0;
	for (i=1; i<=N; i++) 
	{
		scanf("%d",&A[i]);
		if (s<S)
		{
			s+=A[i];
			poz[++poz[0]]=i;
			V[i]=1;
		} else
		{
			s-=A[i];
			neg[++neg[0]]=i;
		}
	}
	while (s!=S)
	{
		if (s<S)
		{
			i=rand() % neg[0] +1;
			V[neg[i]]=1;
			s+=2*A[neg[i]];
			poz[poz[0]++]=neg[i];
			neg[i]=neg[neg[0]];
			neg[0]--;
		} else
		{
			i=rand() % poz[0]  +1 ;
			V[poz[i]]=0;
			s-=2*A[poz[i]];
			neg[neg[0]++]=poz[i];
			poz[i]=poz[poz[0]];
			poz[0]--;
		}
	}
	for (i=1; i<=N; i++) 
		if (V[i]) printf("+"); else printf("-");
}