Cod sursa(job #50814)

Utilizator gigi_becaliGigi Becali gigi_becali Data 8 aprilie 2007 23:36:51
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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()&1) a[++a[0]]=i;else b[++b[0]]=i;
	int suma=0, sumb=0;
	for(i=1;i<=n;i++) if(suma<=sumb) a[++a[0]]=i, suma+=x[i]; else b[++b[0]]=i, sumb+=x[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(ok)
	{
		nr++;
		int p1;
		ok=0;
		
		if(sum<S && b[0]>0)
		{
			
			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;
					if(sum==S) afis();
			}

		}
		else if(sum>S && a[0]>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(sum==S) afis();
			}
		}
			if(sum==S) afis();
			continue;
			
		if(sum==S) afis();
	}
	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();
}