Cod sursa(job #32242)

Utilizator thestickTudor A thestick Data 17 martie 2007 16:39:11
Problema Semne Scor 15
Compilator c Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <math.h>
long n,s,x[50001],ss=0,lim;
char y[50001];

void init()
{
srandom(time(0));
lim=n/4;
}

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;

if(y[i]==1) ss+=x[i];
else ss-=x[i];
}
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);
}

void rez()
{
long i,fl,ct=0;

while(s!=ss)
{
fl=0;i=random()%n;

if(y[i]==0)
        {
                if (  abs(s-ss-2*x[i])  <=  abs(s-ss)  )
                        {       ss+=2*x[i];
                                y[i]=1;
                                fl=1;           }
        }

else
        {
                if (  abs(s-ss+2*x[i]) <=  abs(s-ss)  )
                        {       ss-=2*x[i];
                                y[i]=0;
                                fl=1;           }
        }

if(fl==0)ct++;
if(ct==lim)
        {
                if(y[i]==0)
                        {
                                y[i]=1;
                                ss+=2*x[i];
                        }
                if(y[i]==y)
                        {
                                y[i]=0;
                                ss-=2*x[i];
                        }
                ct=0;
       }
}

}


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