Cod sursa(job #1514)

Utilizator varuvasiTofan Vasile varuvasi Data 13 decembrie 2006 21:53:43
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <iostream>
using namespace std;
#define vmax 500000000
#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];
    }
    int Sdif = (Stotal - S) / 2;    
    fclose(fin);
    
    //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");
    for (i = 1; i <= N; i++)
        if (semne[i]) fprintf(fout, "-");
        else          fprintf(fout, "+");
    fclose(fout);
    return 0;
}