Cod sursa(job #49820)

Utilizator gigi_becaliGigi Becali gigi_becali Data 6 aprilie 2007 14:39:42
Problema Semne Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define maxn 50001

using namespace std;
int a[maxn], b[maxn];
int x[maxn];
int n, S;

void afis()
{
char sol[maxn];

for(int i=1;i<=a[0];i++) sol[a[i]]='+';

for(int i=1;i<=b[0];i++) sol[b[i]]='-';
freopen("semne.out", "w", stdout);
for(int i=1;i<=n;i++) printf("%c", sol[i]);
printf("\n");

exit(0);
	
}
	
int sgn(int a)
{
	if(a<0) return -a;
	return a;
}

void solve()
{
	int i, j;
	for(i=1;i<=n;i++) if((rand()*rand())&1) a[++a[0]]=i;else b[++b[0]]=i;
	
	
	int sum=0;
	for(i=1;i<=a[0];i++) sum+=x[a[i]];
	for(i=1;i<=b[0];i++) sum-=x[b[i]];
	if(sum==S) afis();
//	printf("%d\n", sum);
	int nr=0;
	int ok;
	while(1)
	{
		nr++;
		int p1;
		ok=0;
		if(a[0])
		{
			 p1=(rand()%a[0])+1;
			if(sgn(S-sum) > sgn(S-(sum-(x[a[p1]])<<1))) 
			{
				sum-=x[a[p1]]<<1;
				b[0]++;
				b[b[0]]=a[p1];
				a[p1]=a[a[0]];
				a[0]--;
				ok=1;
			}
		}
		
		if(b[0])
		{
			
			p1=(rand()%b[0])+1;
		
			if(sgn(S-sum)> sgn(S-(sum+(x[b[p1]]<<1))))
			{
				sum+=x[b[p1]]<<1;
				a[0]++;
				a[a[0]]=b[p1];
				b[p1]=b[b[0]];
				b[0]--;
				ok=1;
			}
		}
		
		if(!ok)
		{
			if(a[0]>=b[0])
			{
				p1=(rand()%a[0])+1;
				sum-=x[a[p1]]<<1;
				b[0]++;
				b[b[0]]=a[p1];
				a[p1]=a[a[0]];
				a[0]--;
				ok=1;
			}
			//if(b[0]>a[0])
			else
			{
				p1=(rand()%b[0])+1;
				sum+=x[b[p1]]<<1;
				a[0]++;
				a[a[0]]=b[p1];
				b[p1]=b[b[0]];
				b[0]--;
				ok=1;
			}
		
		}
		
		//printf("%d\n", sum);
		//if(nr>10){ afis();exit(0);}
		if(sum==S) afis();
	}
	
}

	



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