Cod sursa(job #37324)

Utilizator amadaeusLucian Boca amadaeus Data 24 martie 2007 21:38:53
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define NX 50001

#define SHIT 100

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( suma < S ) {
			suma += v[i];
			x[i] = 1;
		}
		else
			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( rand() % 243 < 10 )
		return 1;
	return 0;
}

void pune_semne() {
}
void rez() {
	int l, poz;
	long long dif;

	pune_semne();
	
	while( suma != S ) {
		dif = suma - S;
		if( dif < 0 )
			// cauta un - si schimba in +
			for( l = 0; l < SHIT; l++ ) {
				poz = rand() % N + 1;
				if( x[poz] == 0 )
					break;
			}
		if( dif > 0 )
			// cauta un + si schimba in -
			for( l = 0; l < SHIT; l++ ) {
				poz = rand() % N + 1;
				if( x[poz] == 1 )
					break;
			}
		// 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;
}