Cod sursa(job #1880)

Utilizator blasterzMircea Dima blasterz Data 15 decembrie 2006 11:14:42
Problema Semne Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#define maxn 1<<16

int main()
{
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w",stdout);
	int n,i, x[maxn],v[maxn], S;
	
	scanf("%d %d\n", &n, &S);
	for(i=1;i<=n;i++) scanf("%d", x+i);
	int sum=0, s=0;
	for(i=1;i<=n;i++) sum+=x[i];
	memset(v, 0, sizeof(v));
	time_t q;
	time(&q);
	srand(q%666777);
//	printf("%d %d\n", S, sum);
	while(s!=S)
	{
		s=sum;
		int p;
		memset(v, 0, sizeof(int)*(n+2));
		while(s>S)
		{
			p=1+(int)(	(double)n*rand()/(RAND_MAX+1.0));
			while(v[p] && s-2*x[p] >=S) p=1+(int)((double)n*rand()/(RAND_MAX+1.0));
			v[p]=1;
			s-=2*x[p];
		
			if(s==S) { for(i=1;i<=n;i++) if(v[i]) printf("-"); else printf("+"); printf("\n"); return 0;}
		}
		
	}
	return 0;
}