Cod sursa(job #189967)

Utilizator scvalexAlexandru Scvortov scvalex Data 19 mai 2008 15:41:10
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int S;
int A[50001], NA;
int B[50001], NB;
int C[50001], NC;
long long SA, SB;

int main(int argc, char *argv[]) 
{
	FILE *fi = fopen("semne.in", "r");
	fscanf(fi, "%d %d", &NA, &S);
	NC = NA;
	for (int i(0); i < NA; ++i) {
		fscanf(fi, "%d", A+i);
		C[i] = A[i];
		SA += A[i];
	}
	fclose(fi);

	while (SA - SB != S) {
		if (SA - SB > S) {
			int i = rand() % NA;
      
			SA -= A[i];
			SB += A[i];

			B[NB++] = A[i];
			A[i] = A[--NA];
		} else {
			int i = rand() % NB;

			SA += B[i];
			SB -= B[i];

			A[NA++] = B[i];
			B[i] = B[--NB];
		}
	}

	sort(A, A+NA);
	sort(B, B+NB);

	/*cout << "A: ";
	for (int i(0); i < NA; ++i)
		cout << A[i] << " ";
	cout << endl;

	cout << "B: ";
	for (int i(0); i < NB; ++i)
		cout << B[i] << " ";
		cout << endl;*/

	FILE *fo = fopen("semne.out", "w");
	int i(0), j(0);
	while ((i < NA) || (j < NB)) {
		if ((i < NA) && ((j == NB) || (A[i] < B[j]))) {
			fprintf(fo, "+");
			++i;
		} else {
			fprintf(fo, "-");
			++j;
		}
	}
	fclose(fo);

	return 0;
}