Cod sursa(job #384680)

Utilizator ZillaMathe Bogdan Zilla Data 20 ianuarie 2010 18:21:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define Nmax 50100

long long 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("%lld%lld",&n,&s);
    
    srand(6661233);
    
    for(i=1;i<=n;++i)
        {
            scanf("%lld",&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)
                {
                    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)
                {
                    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;
}