Cod sursa(job #189972)

Utilizator scvalexAlexandru Scvortov scvalex Data 19 mai 2008 15:53:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>

/*  		    
 * Explicatia rezolvarii:
 *                     __
 * +--+ +----+        /  \           +----+      +----+      +----+
 * |  |_|  __+	     /	  \	     |	   \	 |    |	     |	  |
 * |	  /   	    /  __  \	     |	  |\\	 |    |	     |	  |
 * |	 /    	   /  /__\  \	     |	  | \\	 |    |	   __|	  |
 * |	|     	  /    __    \	     |	  |  \\	 |    |	  /   --| |
 * |	|     	 /    /	 \    \	     |	  |   \\_|    |	 |   /	| |    	
 * |	|      	/    / 	  \    \     | 	  |    \      |	  \  \__| |	
 * +----+      +----+  	   +----+    +----+    	+-----+	   \______| 
 *
 * Greu de crezut, dar poeziile mele sunt si mai rele.
 */			 				    	 
							       	 
using namespace std;

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

int main(int argc, char *argv[]) 
{
	FILE *fi = fopen("semne.in", "r");
	fscanf(fi, "%lld %lld", &NA, &S);
	for (int i(0); i < NA; ++i) {
		fscanf(fi, "%lld", 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);

	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;
}