Pagini recente » Atasamentele paginii Clasament emagcluj_10_2016 | Monitorul de evaluare | Atasamentele paginii Clasament simulare-cartita-32 | Rating Lazarescu Sergiu (LazarescuS) | Cod sursa (job #542839)
Cod sursa(job #542839)
// http://infoarena.ro/problema/loto
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
vector<long long> input;
vector<long long> sum;
// calculeaza din nou sumele de trei numere
// pentru a descompune suma gasita
void write(long long toBeFound);
int main() {
bool found = false;
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<long long>::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
write(sum[begin]);
write(sum[end]);
found = true;
break;
}
if(found)
break;
// daca suma cautata este mai mare
while(sum[begin] + sum[end] < dreamedSum && begin!=end)
// reducem intervalul de cautare
begin++;
}
if(!found)
if(sum[begin] + sum[end] == dreamedSum) {
write(begin);
write(end);
}
else
out << "-1";
in.close();
out.close();
return (0);
}
void write(long long toBeFound) {
vector<long long>::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;
}
}