Cod sursa(job #50056)

Utilizator gigi_becaliGigi Becali gigi_becali Data 6 aprilie 2007 19:41:22
Problema Semne Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define maxn 50001
int x[maxn], n, S;
int sgn(int a)
{
	if(a<0) return -a;
	return a;
}


void afis(bool a[])
{
	int i;
	for(i=1;i<=n;i++) if(a[i]) printf("+"); else printf("-");
	printf("\n");
	exit(0);
}


void solve()
{
	bool a[maxn];

	int i, j;
	int sum=0;
	for(i=1;i<=n;i++) a[i]=rand()&1;
	for(i=1;i<=n;i++) if(a[i]) sum+=x[i]; else sum-=x[i];
	
	int p, ok;
	int ntimes=10;
	while(1)
	{
		ok=0;
		if(sum==S) afis(a);
		
		p=(rand()%n)+1;
		for(i=1;i<=ntimes;i++)
		{
		if(a[p] && ( sgn(S-(sum-2*x[p]))  < sgn((S-sum))) ) 
		{
			sum-=2*x[p];
			a[p]=0;
			ok=1;
		}
		if(!a[p] && ( sgn(S-(sum+2*x[p]))  < sgn((S-sum))) )
		{
			sum+=2*x[p];
			a[p]=1;
			ok=1;
		}
		}
		
		if(!ok)
		{
			if(a[p])
			{
				sum-=2*x[p];
				a[p]=0;
			}
			else
			{
				sum+=2*x[p];
				a[p]=1;
			}
		}
		
		if(sum==S) afis(a);
	}
}
		

int main()
{
	time_t s;
	time(&s);
	srand(s%666013);
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);
	scanf("%d %d\n", &n, &S);
	for(int i=1;i<=n;i++) scanf("%d ", x+i);
	solve();
	return 0;
}