Pagini recente » Cod sursa (job #1537752) | Cod sursa (job #1019115) | Cod sursa (job #2561754) | Cod sursa (job #244105) | Cod sursa (job #890547)
Cod sursa(job #890547)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NMax 50010
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%d",&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;
bool cont=true;
while (cont){
cont =false;
for (i=1;i*i<=N;++i){
j=rand()%N+1;
if (sol[j]){
s=sum-2*v[j];
}
else{
s=sum+2*v[j];
}
if (abs(s-S)<abs(sum-S))
{
sol[j]=1-sol[j];
sum=s;
cont=true;
break;
}
}
}
if (sum==S) solved=true;
}
freopen(OUT,"w",stdout);
for (i=1;i<=N;++i) printf("%c",sol[i] ? '+' : '-');
fclose(stdout);
return 0;
}