Cod sursa(job #83057)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 9 septembrie 2007 22:14:44
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<math.h>
#include<iostream.h>
#include<stdlib.h>

long long s, v[50002], n, semn[5002], suma, minus[50000], plus[50002], a, b;

int main()
{
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);

  scanf("%lld %lld", &n, &s);
  srand(time(0)); 
  long long i, x;

  for (i=1; i<=n; i++) { scanf("%lld",&v[i]);
			semn[i]=rand()&1;
			if (semn[i]==0) suma+=v[i], plus[a++]=i;
			else suma-=v[i], minus[b++]=i;}
  

  while (suma!=s)
    {
	if (suma<s)
	{ x=rand()%b;
	  suma+=(v[minus[x]]<<1);
	  semn[minus[x]]=0;
	  plus[++a]=minus[x];
	  minus[x]=minus[b--];
	}
	else
	{ x=rand()%a;
	  suma+=(v[plus[x]]<<1);
	  minus[++b]=plus[x];
	  semn[plus[x]]=1;
	  plus[x]=plus[a--];
	}
    }
  for (i=1; i<=n; i++)
    if (semn[i]==0) 
 	 printf("+");
    else printf("-");
    
  return 0;
}