Cod sursa(job #342605)

Utilizator ZethpixZethpix Zethpix Data 22 august 2009 14:41:31
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
FILE *f,*g;
long s,S,n,i,a[50002],sol[50002];
long BS(long x,long l,long r){
	if(l<=r){
		long m=(l+r)/2;
		if(x<a[m]) BS(x,l,m-1);
		else
		if(x>a[m]) BS(x,m+1,r);
		else
		return m;
	}
	else
		return l;
}
int main(){
	f=fopen("semne.in","r");
	g=fopen("semne.out","w");
	fscanf(f,"%ld%ld",&n,&S);
	for(i=1;i<=n;i++)
		fscanf(f,"%ld",&a[i]);
	srand(time(NULL));
	for(i=1;i<=n;i++){
		sol[i]=rand()%2;
		if(sol[i]) s+=a[i];
		else s-=a[i];
	}
	while(s!=S){
		i=rand()%BS(s-S,1,n);
		if(sol[i]){
			s-=2*a[i];
			sol[i]=0;
		}
		else{
			s+=2*a[i];
			sol[i]=1;
		}
	}
	for(i=1;i<=n;i++)
		if(sol[i]) fprintf(g,"+");
		else fprintf(g,"-");
	fprintf(g,"\n");
	fclose(f);
	fclose(g);
	return 0;
}