Cod sursa(job #340340)

Utilizator savimSerban Andrei Stan savim Data 14 august 2009 12:27:07
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX_N 50010

int poz[MAX_N], neg[MAX_N];
int semn[MAX_N];
int v[MAX_N];
int n, s, sum, ok1, ok2;

void cit() {
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);

	scanf("%d %d", &n, &s);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
		if (sum < s) {
			poz[++poz[0]] = i;
			semn[i] = 1;
			sum += v[i];
		}
		else {
        	neg[++neg[0]] = i;
			sum -= v[i];
		}
	}
}

void solve() {
	srand(time(0));

	while (sum != s) {
    	if (sum < s && neg[0]) {
			//iau din numerele negative
			int k = rand() % neg[0] + 1;
			
			sum += 2 * v[neg[k]];
			semn[neg[k]] = 1;

			poz[++poz[0]] = neg[k];
			neg[k] = neg[neg[0]];
			neg[0]--;
		}
		else {
        	//iau din numerele pozitive
        	int k = rand() % poz[0] + 1;

			sum -= 2 * v[poz[k]];
			semn[poz[k]] = 0;

			neg[++neg[0]] = poz[k];
			poz[k] = poz[poz[0]];
			poz[0]--;
		}
	}
}

void write() {
	for (int i = 1; i <= n; i++)
		if (semn[i]) printf("+");
		else printf("-");
	printf("\n");
}

int main() {

	cit();
	solve();
	write();

	return 0;
}