Cod sursa(job #2211762)

Utilizator skoda888Alexandru Robert skoda888 Data 11 iunie 2018 19:23:34
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb

#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;
}