# Cod sursa(job #1839)

Utilizator Data 14 decembrie 2006 23:19:24 Semne 50 cpp done Arhiva de probleme 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;
}
``````