Pagini recente » Cod sursa (job #247128) | Cod sursa (job #2169201) | Cod sursa (job #3000013) | Cod sursa (job #3147987) | Cod sursa (job #890584)
Cod sursa(job #890584)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define NMax 50010
using namespace std;
typedef long long ll;
const char IN[]="semne.in",OUT[]="semne.out";
int N,solved; ll S;
int v[NMax],sol[NMax];
void randomize(){
for (int i=1;i<=N;++i) sol[i]=rand()%2;
}
int main()
{
int i,j;ll sum,s;
srand(time(NULL));
freopen(IN,"r",stdin);
scanf("%d%lld",&N,&S);
for (i=1;i<=N;++i) scanf("%d",v+i);
fclose(stdin);
while (!solved)
{
sum=0;
randomize();
for (i=1;i<=N;++i)
sum+= sol[i] ? v[i] : -v[i];
if (sum==S) break;
for (i=N;i>0;--i){
if (sol[i]){
s=sum-v[i]-v[i];
}
else{
s=sum+v[i]+v[i];
}
if (abs(s-S)<abs(sum-S))
{
sol[i]^=1;
sum=s;
}
}
if (sum==S) solved=true;
}
freopen(OUT,"w",stdout);
for (i=1;i<=N;++i) printf("%c",sol[i] ? '+' : '-');
fclose(stdout);
return 0;
}