Cod sursa(job #38657)

Utilizator thestickTudor A thestick Data 25 martie 2007 22:52:16
Problema Semne Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <math.h>
#define SLK 50001
long n,s,x[SLK],ss=0,lim,sb;

int y[SLK],z[SLK];

void init()
{
srandom(time(0));
}

void cit()
{
FILE *f;
long i;
f=fopen("semne.in","r");
fscanf(f,"%d %d",&n,&s);
for(i=0;i<n;i++)
{
fscanf(f,"%d",&x[i]);

//if(s>ss)y[i]=1;
//else if(s<ss)y[i]=0;
//else

y[i]=random()%2;
z[i]=y[i];

if(y[i]==1) ss+=x[i];
else ss-=x[i];
sb=ss;
}
fclose(f);
}

void tip()
{
FILE *f;
long i;
f=fopen("semne.out","w");
for(i=0;i<n;i++)
if(y[i]==0)
fprintf(f,"-");
else fprintf(f,"+");
fprintf(f,"\n");
fclose(f);
}

long abso(long nr)
{
return((nr>0)*nr);
return(-(nr<0)*nr);
}

int probabilitate(long celmb,long catac,long cattb)
{
if(abso(cattb-celmb)>=abso(cattb-catac))return 7654;
return 2345;
}

void rez()
{
long i,temp,tz,haicutata;

while(s!=ss)
        for(temp=n/2;(temp>0)&&(s!=ss);temp/=2)
                {

                for(i=0;i<SLK;i++)z[i]=y[i];
                sb=ss;
                
                for(i=0;i<temp;i++)
                        {
                        tz=random()%n;
                        z[tz]=1-z[tz];
                        sb=sb+(z[tz]==1)*(2*x[tz])-(z[tz]==0)*(2*x[tz]);
                        }
                printf("s=%d ss=%d sb=%d\n",s,ss,sb);
                haicutata=(random()%(10000));
                if(probabilitate(ss,sb,s)>haicutata)
                        {
                        for(i=0;i<SLK;i++)y[i]=z[i];
                        ss=sb;
                        }
                }
}


int main()
{
init();
cit();
rez();
tip();
return 0;
}