Cod sursa(job #281248)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 13 martie 2009 22:49:12
Problema Semne Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# define MAXN 50000

long int n,a[MAXN+1];
char semn[MAXN+1];
long long int s;
char sign[2]={'-','+'};
long int mult[2]={-1,1},determinist;
const long int MAXL=(long int)1<<20;
typedef struct {long int val, tata;} NOD;
NOD v[MAXL+1];

long int len;

void citire()
{
     FILE *f=fopen("semne.in","r");
     fscanf(f,"%ld%lld",&n,&s);
     long int i;
     for (i=1;i<=n;i++) fscanf(f,"%ld",&a[i]);
     fclose(f);
}

void scrie()
{
     FILE *g=fopen("semne.out","w");
     long int i;
     for (i=1;i<=n;i++)
         fprintf(g,"%c",sign[semn[i]]);
     fprintf(g,"\n");
     fclose(g);
}

void gen(long int pas, long int final,long int valoare,long int tatal)
{
     if (pas>final) 
        {
        v[++len].val=valoare;
        v[len].tata=tatal;
        }
     else
         {
         gen(pas+1,final,valoare-a[pas],(tatal<<1));
         gen(pas+1,final,valoare+a[pas],(tatal<<1)+1);
         }
}
        
        
int compara(const void *a,const void *b) {return ((NOD*)a)->val-((NOD*)b)->val;}

long int binsearch(long int li, long int lf, long int key)
{
     long int m,i;
     while (li<=lf)
           {
           m=(li+lf)/2;
           if (v[m].val==key)
              {
              //tre' sa scrii niste semne
              for (i=1;i<=determinist;i++)
                  {
                  semn[determinist-i+1]=v[m].tata&1;
                  v[m].tata>>=1;
                  }
              return 1;
              }
           if (v[m].val<key) li=m+1;
           else if (v[m].val>key) lf=m-1;
           }
     return 0;
}
           

int main()
{
    long int ok,index,seed=time(NULL);
    long int i;long long int suma=0;
    determinist=20<n?20 : n;
    //determinist=2;
    srand(seed);
    citire();
    //genereaza_valorile_pt_primele_20
    
    gen(1,determinist,0,0);
    qsort(v,len,sizeof(NOD),compara);
    
    for (i=determinist+1;i<=n;i++) 
        {
        semn[i]=rand()%2;
        suma+=a[i]*mult[semn[i]];
        }
    
    if (determinist>=len)
       {
       ok=binsearch(1,len,s);
       if (ok) 
          {
          scrie();
          return 0;
          }
       }
    else
        for (i=1;i<=22000000;i++)
            {
            index=(rand()%(n-determinist))+determinist+1;
            semn[index]^=1;
            suma=suma+2*a[index]*mult[semn[index]];
            ok=binsearch(1,len,s-suma);
            if (ok) 
               {
               scrie();
               return 0;
               }
            }
    return 0;
}