Cod sursa(job #735409)

Utilizator harababurelPuscas Sergiu harababurel Data 16 aprilie 2012 13:39:24
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main() {
	ifstream f("semne.in");
	ofstream g("semne.out");
	
	srand(time(NULL)); //ca sa nu imi dea acelasi random pentru instante diferite
	
	//IDEE: incep cu toate numerele v[] cu semnul "+"
	//cat timp nu am suma care trebuie, fac urmatoarele chestii:
	//	- daca suma pe care o am e prea mare, caut la intamplare un numar cu "+" pe care sa il fac "-" (il scad din suma)
	//	- daca suma pe care o am e prea mica, caut la intamplare un numar cu "-" pe care sa il fac "+" (il adun la suma)
	//optimizare: daca numaru random pe care l-am ales nu are semnul bun,
	//atunci nu caut altul TOT RANDOM -> il caut in continuare ( while(semn[i]=='- / +') i++; ) 
	//-> ii un pic mai putin riscant asa, pentru ca nu imi alege acelasi numar de mai multe ori
	
	
	int n, v[50005], i;
	long long sbun, s=0;
	char semn[50005];
	
	f>>n>>sbun;
	for(i=1; i<=n; i++) {
		f>>v[i];
		s+=v[i];
		semn[i]='+';
	}
	
	
	while(s!=sbun) { 
		if(s>sbun) { 	//trebuie sa scad un numar -> pun "-" la unu cu "+"
			i=rand()%n + 1;						//aleg o pozitie din sir, la intamplare, si ma folosesc de v[i]
			while(semn[i]=='-' && i<n) i++; 	//daca semnu nu ii bun, ma duc mai departe
			if(semn[i]=='-' && i==n) {			//daca am ajuns la capat si semnu nu ii bun, o iau de la inceput
				i=1;
				while(semn[i]=='-') i++;		//si ma tot duc pana gasesc un semn bun
			}
			
			//am un v[i] cu "+"; 
			semn[i]='-';			//il fac "-"
			s-=2*v[i];				//il scad de 2 ori (o data pentru ca scap de "+" si o data pentru ca primesc un "-")
		}
		
		if(s<sbun) { 	//trebuie sa adun un numar -> pun "+" la unu cu "-"
			i=rand()%n + 1;
			while(semn[i]=='+' && i<n) i++; 
			if(semn[i]=='+' && i==n) {
				i=1; 
				while(semn[i]=='+') i++;
			}
			
			//am un v[i] cu "-";
			semn[i]='+';
			s+=2*v[i];
		}
	}
	
	for(i=1; i<=n; i++) g<<semn[i];
	g<<"\n";
	
	f.close();
	g.close();
	return 0;
}