Cod sursa(job #384244)

Utilizator ZillaMathe Bogdan Zilla Data 19 ianuarie 2010 19:38:02
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define Nmax 50100

int n,s,semn[Nmax],plus[Nmax],minus[Nmax],num[Nmax],st,dr,v1,v2;

int main()
{
    int i;
    
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    scanf("%d%d",&n,&s);
    
    srand(time(0));
    
    for(i=3;i<=n;++i)
        {
            scanf("%d",&num[i]);
            if(st-dr>s)
                {
                    minus[++v2]=i;
                    semn[i]=-1;
                    dr+=num[i];
                }
            else
                {
                    plus[++v1]= i;
                    semn[i]=1;
                    st+=num[i];
                }
        }
        
    while(st-dr!=s)
        {
            if(st-dr>s && v1)
                {
                    int poz=rand()%v1+1;
                    st-=num[plus[poz]];
                    dr+=num[plus[poz]];
                    semn[plus[poz]]*=-1;
                    minus[++v2]=plus[poz];
                    plus[poz]=plus[v1--];     
                }    
            if(st-dr<s && v2)
                {
                    int poz=rand()%v2+1;
                    st+=num[minus[poz]];
                    dr-=num[minus[poz]];
                    semn[minus[poz]]*=-1;
                    plus[++v1]=minus[poz];
                    minus[poz]=minus[v2--];    
                }
        }
        
    for(i=1;i<=n;++i)
        if(semn[i]>0)
            printf("+");
        else
            printf("-");
             
    printf("\n");
    return 0;
}