Cod sursa(job #928585)

Utilizator timicsIoana Tamas timics Data 26 martie 2013 15:41:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int N,q1[50100],q2[50100],a[50100];
char b[50100];
long long s=0,t=0;

int main()
{
    srand(time(0));
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    scanf("%d%lld",&N,&s);
    int f1=1;
    int l1=0;
    int f2=1;
    int l2=0;

    for(int i=1;i<=N;++i)
    {
        scanf("%d",&a[i]);
        ++l1;
        q1[l1]=i;
        t=t-a[i];
        b[i]='-';
    }

    while(t!=s)
    {
        if(t<s)
        {
            int x=rand()%l1+1;
            t=t+2*a[q1[x]];
            ++l2;
            q2[l2]=q1[x];
            b[q1[x]]='+';
            q1[x]=q1[l1];
            --l1;
        }

        if(t>s)
        {
            int x=rand()%l2+1;
            t=t-2*a[q2[x]];
            ++l1;
            q1[l1]=q2[x];
            b[q2[x]]='-';
            q2[x]=q2[l2];
            --l2;
        }
    }

    for(int i=1;i<=N;++i)
        printf("%c",b[i]);

    return 0;
}