Cod sursa(job #91996)

Utilizator 100puncteIonut Popa 100puncte Data 14 octombrie 2007 02:26:53
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<stdlib.h>

long long s, v[50102], n, semn[50102], suma, minus[50100], plus[50102], 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]);

  for(i=1; i<=n; i++)
  {
    if (suma+v[i]<=s)
    {
      plus[++a]=i;
      suma+=v[i];
      semn[i]=1;
     }
      else
     {
      minus[++b]=i;
      suma-=v[i];
      semn[i]=0;
     }
   }
  		
  srand(time(0));   

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