Cod sursa(job #66243)

Utilizator info_arrandrei gigea info_arr Data 17 iunie 2007 00:03:46
Problema Semne Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
using namespace std;

#define MAX_N 50005

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>

FILE *fin=fopen("semne.in","r"),
     *fout=fopen("semne.out","w");
   
int n,i,sp,sm,s;
int a[MAX_N];
short p[MAX_N];   
     
int searchp(int x)
{
   int m,li=1,lf=n;
   while (li<=lf)
    {
      m=(li+lf)/2;
      if (x<a[m]) lf=m-1;
      if (x>a[m]) li=m+1;
      if (x==a[m]) break;
    }
   if (x==a[m] && p[m]==1) return m;
    else return -1;
}           
     
int main()
{   
    fscanf(fin,"%d %d\n",&n,&s);
    memset(p,0,sizeof(p));
    for (i=1; i<=n; i++)
    {
     fscanf(fin,"%d",a+i);
     sp+=a[i]; p[i]=1;
    }
    int c,v;
    while (sp-sm!=s) 
     {
      c=rand() % n ;  
      if (sp-sm>s)
       {
         v=searchp((sp-sm)/2);  
         if (v!=-1) 
          {
            sp-=a[v]; sm+=a[v];
            p[v]=0;
            break;
          }  
       }      
      if (sp-sm>s && p[c]==1)
       {
         sp-=a[c]; sm+=a[c];
         p[c]=0;
         continue;
       }
      if (sp-sm<s && p[c]==0)
       {
         sp+=a[c]; sm-=a[c];
         p[c]=1;
         continue;
       }
     }
    for (i=1; i<=n; i++) 
     if (p[i]==1) fprintf(fout,"+");
      else fprintf(fout,"-");                    
    
    fclose(fin); fclose(fout);  
      
    return 0;
}