Pagini recente » Cod sursa (job #356561) | Cod sursa (job #60575) | Cod sursa (job #992337) | Cod sursa (job #499622) | Cod sursa (job #735403)
Cod sursa(job #735403)
#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;
}