Cod sursa(job #3130760)

Utilizator FlaviaF7Fota Stefania-Flavia FlaviaF7 Data 18 mai 2023 15:32:31
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

struct Combinari {
    long long suma;
    int nr1, nr2, nr3;

    bool operator<(const Combinari& obj) const {
        return suma < obj.suma;
    }
};

vector<int> generareBilet(const vector<int>& numere, int sumaCeruta) {
    vector<Combinari> combinari;
    int n = numere.size();

    // Generarea tuturor combinarilor posibile de 3 numere
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int t = j; t < n; t++) {
                long long suma = numere[i] + numere[j] + numere[t];
                combinari.push_back({ suma, i, j, t });
            }
        }
    }

    sort(combinari.begin(), combinari.end());

    // Cautăm o combinare care ajunge la suma cerută
    vector<int> bilet;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int t = j; t < n; t++) {
                long long sumaRamasa = sumaCeruta - numere[i] - numere[j] - numere[t];
                Combinari combinareCeruta = { sumaRamasa, -1, -1, -1 };

                auto it = lower_bound(combinari.begin(), combinari.end(), combinareCeruta);
                if (it != combinari.end() && it->suma == sumaRamasa) {
                    bilet = { numere[i], numere[j], numere[t], numere[it->nr1], numere[it->nr2], numere[it->nr3] };
                    return bilet;
                }
            }
        }
    }
    
    return bilet;
}

int main() {
    
    int n;
    long long s;
    in >> n >> s;
    vector<int> numere(n);
    for (int i = 0; i < n; i++) {
        in >> numere[i];
    }

    vector<int> bilet = generareBilet(numere, s);

    if (bilet.empty()) {
        out << -1;
    } else {
        for (int i = 0; i < 6; i++) {
            out << bilet[i] << " ";
        }
    }

    in.close();
    out.close();
    return 0;
}