Cod sursa(job #785927)

Utilizator ephgstefana gal ephg Data 10 septembrie 2012 10:26:44
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
#define BM 50005
long long sf,s[BM];
int n,plus[BM],minus[BM],dimp,dimm;
char out[BM];
int main () {
	int i,el;
	long long sc=0;
	srand(time(NULL));
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	scanf("%d %lld",&n,&sf);
	for(i=1;i<=n;++i)scanf("%d",&s[i]);
	for(i=1;i<=n;++i){
		if(sc>sf){
			sc-=s[i];
			out[i]='-';
			minus[++dimm]=i;
		}
		else {
			sc+=s[i];
			out[i]='+';
			plus[++dimp]=i;
		}
	}
	for(;sc!=sf;){
		if(sc<sf){
			el=rand()%dimm+1;
			sc+=(2*s[minus[el]]);
			out[minus[el]]='+';
			plus[++dimp]=minus[el];
			swap(minus[el],minus[dimm]);
			--dimm;
		}
		else {
			el=rand()%dimp+1;
			sc-=(2*s[plus[el]]);
			out[plus[el]]='-';
			minus[++dimm]=plus[el];
			swap(plus[el],plus[dimm]);
			--dimp;
		}
	}
	for(i=1;i<=n;++i)printf("%c",out[i]);
	return 0;
}