Pagini recente » Cod sursa (job #169365) | Cod sursa (job #3165483) | Cod sursa (job #2804926) | Cod sursa (job #2323172) | Cod sursa (job #37324)
Cod sursa(job #37324)
#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;
}