Cod sursa(job #37281)

Utilizator amadaeusLucian Boca amadaeus Data 24 martie 2007 19:43:51
Problema Semne Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define NX 50001

using namespace std;

long long suma, S, newsum;

int v[ NX ], N;
bool x[ NX ];

void cit() {
	scanf( "%d%lld", &N, &S );
	for( int i = 1; i <= N; i++ ) {
		scanf( "%d", v + i );
		if( rand() % 2 )
			x[i] = true;
		suma = x[i] ? suma + v[i] : suma - v[i];
	}
}

inline
long long ABS( long long x ) {
	return x < 0 ? -x : x;
}

bool Eris() {
	if( ABS( S - suma ) > ABS( S - newsum ) )
		return 1;
	if( 1 / ( rand() % 10 + 1 ) < 0.2 )
		return 1;
	return 0;
}

void rez() {
	int poz;
	while( suma != S ) {
		poz = rand() % N + 1;
		// x[i] == 1 -> semnul este plus
		newsum = suma + 2 * ( x[poz] ? -v[poz] : v[poz] );
		if( Eris() ) {
			x[poz] = 1 - x[poz];
			suma = newsum;
		}
	}
}

void scr() {
	for( int i = 1; i <= N; i++ )
		if( x[i] )
			printf( "+" );
		else
			printf( "-" );
}

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

	srand( time( 0 ) );
	cit();
	rez();
	scr();

	return 0;
}