Cod sursa(job #14686)

Utilizator victorsbVictor Rusu victorsb Data 9 februarie 2007 14:40:32
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <time.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define Nmax 50005

int n, s;
int sir[Nmax], tip[Nmax];

void citire()
{
    int i;
    scanf("%d %d\n", &n, &s);
    for (i=1; i<=n; ++i)
        scanf("%d ", &sir[i]);
}

void solve()
{
    int i;
    long long suma = 0, sum, tmp;
    srand(time(0));
    reverse(sir+1, sir+n+1);
    for (i=1; i<=n; ++i)
        suma += sir[i];
    tmp = suma;
    do
    {
        sum = s;
        suma = tmp;
        for (i=1; i<=n; ++i)
        {
            if (sum + sir[i] > suma - sir[i])
                tip[i] = 1;
            else if (sum - sir[i] < - suma + sir[1])
                tip[i] = -1;
            else
                tip[i] = 1 - (2 * (rand() % 2));
            if (tip[i] == 1)
                sum -= sir[i];
            else sum += sir[i];
            suma -= sir[i];
        }
        /*
        printf("%d\n", sum);
        for (i=1; i<=n; ++i)
            printf("%d ", tip[i]);
        printf("\n\n");
        */
    }
    while (sum);
    reverse(tip+1, tip+n+1);
    for (i=1; i<=n; ++i)
        if (tip[i] == 1)
            printf("+");
        else
            printf("-");
}

int main()
{
    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);
    citire();
    solve();
    return 0;
}