Cod sursa(job #785922)

Utilizator ephgstefana gal ephg Data 10 septembrie 2012 10:21:01
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
#define BM 50005
long long sf;
int s[BM],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*minus[el]);
			out[el]='+';
			plus[++dimp]=minus[el];
			swap(minus[el],minus[dimm]);
			--dimm;
		}
		else {
			el=rand()%dimp+1;
			sc-=(2*plus[el]);
			out[el]='-';
			minus[++dimm]=plus[el];
			swap(plus[el],plus[dimm]);
			--dimp;
		}
	}
	for(i=1;i<=n;++i)printf("%c",out[i]);
	return 0;
}