Cod sursa(job #37367)

Utilizator vmaneavmanea vmanea Data 24 martie 2007 22:31:51
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 50001
#define infinit 2000000000

int N, S, i, A[nmax], X[nmax], suma, X1[nmax], t, minim;

int main(void)
{
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);

	minim = infinit;

	scanf("%d%d", &N, &S);

	for (i = 1; i <= N; ++i)
		scanf("%d", &A[i]);

//	randomize();

	for (; minim;)
	{
		suma = 0;
		for (i = 1; i <= N; ++i)
		{
			X1[i] = rand() % 2;
			if (X1[i] == 0)
				X1[i]--;

			suma += X1[i] * A[i];
		}

		if (abs(suma - S) < minim)
		{
			minim = suma - S;
			if (minim < 0) minim = -minim;

			for (i = 1; i <= N; ++i)
				X[i] = X1[i];

		}
		if (abs(suma + S) < minim)
		{
			minim = suma + S;
			if (minim < 0) minim = -minim;

			for (i = 1; i <= N; ++i)
				X[i] = -X1[i];

		}
	}

	for (i = 1; i <= N; ++i)
		if (X1[i] == 1) printf("+");
		else printf("-");

		printf("\n");

	return 0;
}