Cod sursa(job #735620)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 16 aprilie 2012 21:24:52
Problema Semne Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<cstdlib>
#define dim 30007
using namespace std;

ifstream f("semne.in");
ofstream g("semne.out");
char sol[dim];
long t,i;
int Ss,S;
long long a[dim];
int p[dim],m[dim],mm,pp,n;
int main () {
	
	
	f>>n>>S;
	
	for(i=1;i<=n;i++){
		
		f>>a[i];
		int t=rand()%2;
		
		if(t){
			p[++pp]=i;
			
			Ss+=a[i];
			sol[i]='+';
		}
		else{
			m[++mm]=i;
			sol[i]='-';
			Ss-=a[i];
		}
	}
	while(Ss!=S){
		
		
		if ( Ss<S  ) {
			
			int t=rand()%mm+1;
			
			p[++pp]=m[t];
			m[t]=m[mm--];
			sol[p[pp]]='+';
			Ss+=2*a[p[pp]];
		}
		else {
			
			int t=rand()%pp+1;
			
			m[++mm]=p[t];
			p[t]=p[pp--];
			Ss-=2*a[m[mm]];
			sol[m[mm]]='-';
		}
	}
	
	
	for(i=1;i<=n;i++)
		g<<sol[i];
	return 0;
}