Cod sursa(job #890547)

Utilizator crushackPopescu Silviu crushack Data 25 februarie 2013 10:21:29
Problema Semne Scor 25
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.99 kb
#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;
}