Cod sursa(job #348208)

Utilizator prdianaProdan Diana prdiana Data 14 septembrie 2009 21:00:41
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 50002

long long i,n,nrn,nrp,s,sum;
long long poz[MAXN],neg[MAXN],a[MAXN],x;
char sign[MAXN];


int main()
{
	srand(time(NULL));
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	scanf("%d%d",&n,&s);

	for (i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		if (sum+a[i]<=s)
		{
			nrp++;
			poz[nrp] = i;
			sign[i] = '+';
			sum+=a[i];
		}
		else
		{
			nrn++;
			neg[nrn] = i;
			sign[i] = '-';
			sum-=a[i];
		}
	}

	while (sum!=s)
	{
		if (sum<s)
		{
			x = rand()%nrn + 1;
			sign[neg[x]] = '+';
			sum+=2*a[neg[x]];
			nrp++;
			poz[nrp] = neg[x];
			neg[x] = neg[nrn];
			nrn--;
		}
		else
		{
			x = rand()%nrp + 1;
			sign[poz[x]] = '-';
			sum-=2*a[poz[x]];
			nrn++;
			neg[nrn] = poz[x];
			poz[x] = poz[nrp];
			nrp--;

		}
	}
	for (i=1;i<=n;i++)
	{
		printf("%c ",sign[i]); 
	}

	return 0;
}