Cod sursa(job #348101)

Utilizator prdianaProdan Diana prdiana Data 13 septembrie 2009 23:12:07
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 50002

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

int main()
{
	srand(time(NULL));
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);

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

	while (suma!=s)
	{
		if (suma<s)
		{
			x = rand()%nrn;
			suma+=2*a[neg[x]];
			nrp++;
			poz[nrp] = neg[x];
			semn[neg[x]] = '+';
			neg[x] = neg[nrn];
			nrn--;
		}
		else
		{
			x = rand()%nrp;
			suma-=2*a[poz[x]];
			nrn++;
			neg[nrn] = poz[x];
			semn[poz[x]] = '-';
			poz[x] = poz[nrp];
			nrp--;
		}
	}
	for (i=0;i<n;i++)
	{
		printf("%c ",semn[i]);
	}
	return 0;
}