Pagini recente » Cod sursa (job #2338574) | Cod sursa (job #1866765) | Cod sursa (job #1158991) | Cod sursa (job #2563006) | Cod sursa (job #533157)
Cod sursa(job #533157)
// http://infoarena.ro/problema/loto
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
vector<int> input;
vector<int> sum;
// calculeaza din nou sumele de trei numere
// pentru a descompune suma gasita
void firstWrite(int toBeFound);
void secondWrite(int toBeFound);
int main() {
int number,dreamedSum,tmp;
in >> number >> dreamedSum;
for(int i=1;i<=number;i++) {
in >> tmp;
input.push_back(tmp);
}
// calculam toate sumele de trei numere
// (suma cautate de noi, de sase numere,
// va fi suma a doua sume de trei numere)
vector<int>::iterator first,second,third;
for(first=input.begin();first!=input.end();first++)
for(second=input.begin();second!=input.end();second++)
for(third=input.begin();third!=input.end();third++)
sum.push_back(*first+*second+*third);
// sortam in ordine crescatoare
sort(sum.begin(),sum.end());
// cu iteratori depaseste timpul de executie
int begin = 0;
int end = sum.size() - 1;
// parcurgem sumele de la capete pana acestea se intalnesc
while(begin != end) {
// daca suma cautata este mai mica
while(sum[begin] + sum[end] > dreamedSum && end!=begin)
// reducem intervalul in care cautam
end--;
// daca am gasit suma dorita
if(sum[begin] + sum[end] == dreamedSum) {
// calculam din nou sumele de trei numere
// si afisam numerele
firstWrite(sum[begin]);
secondWrite(sum[end]);
return (0);
}
// daca suma cautata este mai mare
while(sum[begin] + sum[end] < dreamedSum && begin!=end)
// reducem intervalul de cautare
begin++;
}
out << "-1\n";
return (0);
}
void firstWrite(int toBeFound) {
vector<int>::iterator first,second,third;
for(first=input.begin();first!=input.end();first++)
for(second=input.begin();second!=input.end();second++)
for(third=input.begin();third!=input.end();third++)
if(*first + *second + *third == toBeFound) {
out << *first << " " << *second << " " << *third << " ";
return;
}
}
void secondWrite(int toBeFound) {
vector<int>::reverse_iterator first,second,third;
for(first=input.rbegin();first!=input.rend();first++)
for(second=input.rbegin();second!=input.rend();second++)
for(third=input.rbegin();third!=input.rend();third++)
if(*first + *second + *third == toBeFound) {
out << *first << " " << *second << " " << *third << " ";
return;
}
}