Cod sursa(job #4191)

Utilizator vlad_DVlad Dumitriu vlad_D Data 31 decembrie 2006 21:50:22
Problema Semne Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <time.h>
#define maxx 1000
using namespace std;

struct per{long long val, ind;};

long long n, i, j, best;
long long s1= 0, s2= 0,  pos;

vector <per> poz, neg;
vector <per> bb;
long long abs2 (long long B) {
	if (B < 0) return -B;
	return B;
	}
long long S;
int main() {
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%lld", &n);
srand(time(0)/123);
n++;
for (i=0; i<n; i++) {
	int X;
	scanf("%lld", &X);
if (i==0) S = X;
	per A;
	A.val = X; A.ind = i;
	if (rand()%2 == 0) {
	poz.push_back(A);
	s1+=X;}
	else {neg.push_back(A); s2+=X;}
	}

best = -1;
//for (i=1; i<=maxx; i++) 
while (1)
{

	if (s1 > s2&& poz.size()>0) {
		pos = rand()%poz.size();
		s1-=poz[pos].val;
		s2+=poz[pos].val;
		neg.push_back(poz[pos]);
    	poz[pos] = poz[poz.size()-1]; poz.pop_back();
		}
	 if (s2 > s1 && neg.size() >0){
		pos = rand()%neg.size();
		s1+=neg[pos].val;
		s2-=neg[pos].val;
		poz.push_back(neg[pos]);
		neg[pos] = neg[neg.size()-1]; neg.pop_back();
		}
	if (s1 == s2) break;
	}
int sol[50010];
for (i=0; i<poz.size(); i++) sol[poz[i].ind+1] =  1;
for (i=0; i<neg.size(); i++) sol[neg[i].ind+1] = -1;
if (sol[1] == 1) s1-=S; else s2-=S;
if (s1 < s2) for (i=2; i<=n; i++) sol[i]*=-1;
for (i=2; i<=n; i++) {
		if (sol[i] ==1) printf("+"); else printf("-");}
printf("\n");
}