Cod sursa(job #322492)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 8 iunie 2009 22:40:29
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
FILE*fin=fopen("semne.in","r");
FILE*fout=fopen("semne.out","w");
#define ll long long
#define nm 50005
int a[nm],a1[nm],a2[nm],n;
char ans[nm];
int main()
{
  ll sum,sum1=0,sum2=0;
  int i,d1=0,d2=0,aux,poz;  
  fscanf(fin,"%d%lld",&n,&sum);  
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&a[i]);
  for(i=1;i<=n;i++)
    if(sum1<sum2)
    {
      a1[++d1]=i;
      sum1+=a[i];
    }  
    else 
    {
      a2[++d2]=i;
      sum2+=a[i];
    }
  srand(time(0));
  while((sum1-sum2)!=sum)
  {
    //tre sa adaug la sum1                     
    if(sum1-sum2<sum)
    {
      poz=rand()%d2+1;
      aux=a2[poz];
      a2[poz]=a2[d2];
      a2[d2]=aux;
      sum2-=a[a2[d2]];
      sum1+=a[a2[d2]];
      a1[++d1]=a2[d2];
      d2--;
    }
    else    //tre sa adaug la sum2
    {
      poz=rand()%d1+1;
      aux=a1[poz];
      a1[poz]=a1[d1];
      a1[d1]=aux;
      sum1-=a[a1[d1]];
      sum2+=a[a1[d1]];
      a2[++d2]=a1[d1];
      d1--;
    }
  }
  for(i=1;i<=d1;i++)
    ans[a1[i]]='+';
  for(i=1;i<=d2;i++)
    ans[a2[i]]='-';
  for(i=1;i<=n;i++)
    fprintf(fout,"%c",ans[i]);    
  fclose(fin);
  fclose(fout);
  return 0;
}