Cod sursa(job #342606)

Utilizator ZethpixZethpix Zethpix Data 22 august 2009 14:46:17
Problema Semne Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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 0;
}
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];
		if(s>S)
			if(sol[i]){
				sol[i]=0;
				s-=2*a[i];
			}
			else{
				sol[i]=1;
				s+=2*a[i];
			}
	}
	while(s!=S){
		i=BS(s-S,1,n);
		if(i==0) i=rand()%(rand()%n+1)+1;
		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;
}