Pagini recente » Cod sursa (job #1450209) | Borderou de evaluare (job #1569690) | Monitorul de evaluare | Cod sursa (job #666365) | Cod sursa (job #986127)
Cod sursa(job #986127)
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define Nmax 50005
int N, S, suma, r;
int a[Nmax];
int pozi[Nmax], nega[Nmax];
int semne[Nmax];
void read()
{
ifstream f("semne.in");
f >> N >> S;
srand( time( NULL ) );
for ( int i = 1; i <= N; ++i )
{
f >> a[i];
r = rand() % 2;
if( r )
{
semne[i] = 1;
suma += a[i];
pozi[ ++pozi[0] ] = i;
}
else
{
semne[i] = -1;
suma -= a[i];
nega[ ++nega[0] ] = i;
}
}
f.close();
}
void semneve()
{
while( suma != S )
{
if( suma < S )
{
r = ( rand() % pozi[0] ) + 1;
suma += 2 * a[ pozi[r] ];
semne[ pozi[r] ] = 1;
nega[ ++nega[0] ] = pozi[r];
pozi[r] = pozi[ pozi[0]-- ];
}
if(suma>S)
{
r = ( rand() % nega[0] ) + 1;
suma -= 2 * a[ nega[r] ];
semne[ nega[r] ] = -1;
pozi[ ++pozi[0] ] = nega[r];
nega[r] = nega[ nega[0]-- ];
}
}
}
void print()
{
ofstream g("semne.out");
for ( int i = 1; i <= N; ++i )
{
if ( semne[i] == 1 )
g << "+";
else
g << "-";
}
g << "\n";
g.close();
}
int main()
{
read();
semneve();
print();
return 0;
}