Cod sursa(job #1660)

Utilizator varuvasiTofan Vasile varuvasi Data 14 decembrie 2006 11:58:53
Problema Semne Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <iostream>
using namespace std;
#define vmax 100000000
#define vvmax 1000000000
#define nmax 50001
int N;
int Stotal, S;
int t[vmax];
int v[vmax];
int a[nmax];
int semne[nmax];

int main()
{
    int i = 0, j = 0;
    FILE *fin = fopen("semne.in", "rt");
    fscanf(fin, "%d %d", &N, &S);
    for (i = 1; i <= N; i++)
    {
        fscanf(fin, "%d", &a[i]);
        Stotal += a[i];
    }
    fclose(fin);
    
    int minus = 0;
    int Sdif = (Stotal - S) / 2;
    if (S < 0) Sdif = Stotal - Sdif, minus = 1;

    //cout << Sdif << " " << Stotal << " " << S << '\n';
    //cin.get();
    v[0] = 1;
    for (i = 1; i <= N; i++)
        for (j = Sdif; j >= 0; j--)
            if (v[j] && j + a[i] <= Sdif)
            {
                if (v[j + a[i]]) continue;
                v[j + a[i]] = 1;
                t[j + a[i]] = i;
            }
    
   /* for (i = 1; i <= Sdif; i++)
        cout << v[i] << ' ';
    cout << '\n';
    for (i = 1; i <= Sdif; i++)
        cout << t[i] << ' ';
    cin.get();*/
    i = Sdif;
    while (i)
    {
        semne[t[i]] = 1;
        i -= a[t[i]];
    }
    
    FILE *fout = fopen("semne.out", "wt");
    if (minus == 0)
    for (i = 1; i <= N; i++)
        if (semne[i]) fprintf(fout, "-");
        else          fprintf(fout, "+");
    else 
    for (i = 1; i <= N; i++)
        if (semne[i]) fprintf(fout, "+");
        else          fprintf(fout, "-");
        
    fclose(fout);
    return 0;
}