Cod sursa(job #844567)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 29 decembrie 2012 15:19:31
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<iostream>
#include<fstream>
#include<time.h>
#include<stdlib.h>
using namespace std;

#define NMAX 50001

int v[NMAX],semn[NMAX],p[NMAX],m[NMAX];

int main ()
{
	int i,n,sum,s,x;
	ifstream f("semne.in");
	ofstream g("semne.out");
	f>>n>>s;
	sum=0;
	srand(time(NULL));
	for(i=1;i<=n;i++) {
		f>>v[i];
		if(sum<=s) {
			sum=sum+v[i];
			p[++p[0]]=i;
		}
		else {
			semn[i]=1;
			sum=sum-v[i];
			m[++m[0]]=i;
		}
	}
	f.close();
	while(sum!=s) 
		if(sum<s) {
			x=rand()%(m[0])+1;
			semn[m[x]]=0;
			sum=sum+2*v[m[x]];
			swap(m[x],m[m[0]]);
			m[0]--;
			p[++p[0]]=m[x];
		}
		else {
			x=rand()%(p[0])+1;
			semn[p[x]]=1;
			sum=sum-2*v[p[x]];
			swap(p[x],p[p[0]]);
			p[0]--;
			m[++m[0]]=p[x];
		}
	for(i=1;i<=n;i++)
		if(semn[i]==0)
			g<<'+';
		else g<<'-';
	g<<'\n';
	g.close();
	return 0;
}