Cod sursa(job #91225)

Utilizator razvi9Jurca Razvan razvi9 Data 11 octombrie 2007 21:43:05
Problema Semne Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<stdlib.h>
long sa,sb,s;
int a[50001],b[50001],na,nb,n,x[50001],i;
int main()
{freopen("semne.in","r",stdin);
 freopen("semne.out","w",stdout);
 scanf("%d %lld",&n,&s);
 na=n/2;nb=n-na;
 for(i=1;i<=n;i++)
 {scanf("%d",&x[i]);
  if(i<=na) {a[i]=i;sa+=x[i];}
   else {b[i-na]=i;sb+=x[i];}
   }
 while((sa-sb)!=s)
 {while((sa-sb)>s)
   {i=rand()%na+1;
    b[++nb]=a[i]; sa=sa-x[a[i]];sb=sb+x[a[i]];
    a[i]=a[na];
    a[na]=0;
    --na;}
  while((sa-sb)<s)
   {i=rand()%nb+1;
    a[++na]=b[i]; sa=sa+x[b[i]];sb=sb-x[b[i]];
    b[i]=b[nb];
    b[nb]=0;
    --nb;}
  } 
 for(i=1;i<=na;i++) x[a[i]]=-1;
 for(i=1;i<=n;i++)
  if(x[i]==-1) printf("+");
   else printf("-");
 fclose(stdout); }