Pagini recente » Cod sursa (job #3151411) | Cod sursa (job #497904) | Cod sursa (job #3270786) | Cod sursa (job #2735125) | Cod sursa (job #2211762)
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
struct Sume_de_trei{
long suma;
long a;
long b;
long c;
};
long poz_pereche = -1;
void switch_elements(int poz_1, int poz_2, std::vector<Sume_de_trei>& vect)
{
Sume_de_trei temp = vect[poz_1];
vect[poz_1] = vect[poz_2];
vect[poz_2] = temp;
}
void quicksort(int inf, int sup, std::vector<Sume_de_trei>& s)
{
int mijloc = (inf + sup) / 2;
int i = inf;
int j = sup;
do{
while(i < sup && s[i].suma < s[mijloc].suma) ++i;
while(j > inf && s[j].suma > s[mijloc].suma) --j;
if(i <= j){
switch_elements(i, j, s);
++i;
--j;
}
} while(i <= j);
if(i < sup) quicksort(i, sup, s);
if(j > inf) quicksort(inf, j, s);
}
bool cautare_binara(int inf, int sup, std::vector<Sume_de_trei>& s, int num_cautat)
{
while(inf <= sup){
int mijloc = (inf + sup) / 2;
if(num_cautat > s[mijloc].suma){
inf = mijloc + 1;
}
else if(num_cautat < s[mijloc].suma){
sup = mijloc - 1;
}
else{
poz_pereche = mijloc;
return true;
}
}
return false;
}
int main()
{
std::ifstream in("loto.in");
std::ofstream out("loto.out");
int N;
long S;
in >> N >> S;
std::set<long> numere;
long x;
while(in >> x){
numere.insert(x);
}
std::vector<Sume_de_trei> sume;
for(std::set<long>::iterator i = numere.begin(); i != numere.end(); ++i){
for(std::set<long>::iterator j = numere.begin(); j != numere.end(); ++j){
for(std::set<long>::iterator k = numere.begin(); k != numere.end(); ++k){
Sume_de_trei nou;
nou.suma = *i + *j + *k;
nou.a = *i;
nou.b = *j;
nou.c = *k;
sume.push_back(nou);
}
}
}
// for(std::vector<Sume_de_trei>::iterator it = sume.begin(); it != sume.end(); ++it){
// std::cout << it->suma << ' ';
//}
long sume_size = sume.size();
quicksort(0, sume_size - 1, sume);
bool found = false;
for(int i = 0; i < sume_size; ++i){
if(cautare_binara(0, sume_size - 1, sume, S - sume[i].suma)){
out << sume[i].a << ' ' <<sume[i].b << ' ' <<sume[i].c << ' ';
out << sume[poz_pereche].a << ' ' << sume[poz_pereche].b << ' ' <<sume[poz_pereche].c;
break;
}
std::cout << '^';
}
if(poz_pereche == -1){
out << -1;
}
return 0;
}