Cod sursa(job #210034)

Utilizator AndreyPAndrei Poenaru AndreyP Data 26 septembrie 2008 10:04:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 50005
long long v[N];
char semn[N];
int plus[N],minus[N];
long long s,s1;
int n;
void citire()
{
	scanf("%d%lld",&n,&s);
	for(int i=1; i<=n; i++)
	{
		scanf("%lld",&v[i]);
		if((long long)s1<s)
		{
			s1+=v[i];
			plus[++plus[0]]=i;
			semn[i]='+';
		}
		else
		{
			s1-=v[i];
			minus[++minus[0]]=i;
			semn[i]='-';
		}
	}
}
void rezolva()
{
	srand(time(NULL));
	int aux;
	while((long long)s1!=s)
	{
		if((long long)s1<s)
		{
			aux=rand()%minus[0]+1;
			s1+=v[minus[aux]]<<1;
			semn[minus[aux]]='+';
			plus[++plus[0]]=minus[aux];
			minus[aux]=minus[minus[0]--];
		}
		else
		{
			aux=rand()%plus[0]+1;
			s1-=v[plus[aux]]<<1;
			semn[plus[aux]]='-';
			minus[++minus[0]]=plus[aux];
			plus[aux]=plus[plus[0]--];
		}
	}
}
int main()
{
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	citire();
	rezolva();
	fputs(semn+1,stdout);
	printf("\n");
	return 0;
}