Cod sursa(job #284031)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 20 martie 2009 21:41:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# define MAXN 50000

long int n,a[MAXN+1],poz[MAXN+1],pozlen,neg[MAXN+1],neglen;
char semn[MAXN+1];
long long int s;
char sign[2]={'-','+'};

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);
}        

int main()
{
    long int ok,index,seed=time(NULL),i;
    long long int suma=0;
    srand(seed);
    citire();
    
    for (i=1;i<=n;i++) 
        {
        if (suma<s) semn[i]=1;
        else semn[i]=0;
        if (semn[i]) {poz[++pozlen]=i;suma+=a[i];}
        else {neg[++neglen]=i;suma-=a[i];}
        }
        
    for (;;)
            {
            while (suma<s && neglen)
                  {
                  index=(rand()%neglen)+1;
                  suma+=2*a[neg[index]];
                  semn[neg[index]]^=1;
                  poz[++pozlen]=neg[index];
                  neg[index]=neg[neglen];
                  neglen--;
                  }
            if (s==suma) {scrie();return 0;}
            while (suma>s && pozlen)
                  {
                  index=(rand()%pozlen)+1;
                  suma-=2*a[poz[index]];
                  semn[poz[index]]^=1;
                  neg[++neglen]=poz[index];
                  poz[index]=poz[pozlen];
                  pozlen--;
                  }
            //printf(" %ld %ld \n",suma,s);
            if (s==suma) {scrie();return 0;}
            }
    return 0;
}