Cod sursa(job #3130757)

Utilizator FlaviaF7Fota Stefania-Flavia FlaviaF7 Data 18 mai 2023 15:23:08
Problema Loto Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 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 };

                bool found = false;
                for (int k = 0; k < combinari.size(); k++) {
                    if (combinari[k].suma == sumaRamasa) {
                        bilet = { numere[i], numere[j], numere[t], numere[combinari[k].nr1], numere[combinari[k].nr2], numere[combinari[k].nr3] };
                        found = true;
                        break;
                    }
                }

                if (found) {
                    break;
                }
            }

            if (!bilet.empty()) {
                break;
            }
        }

        if (!bilet.empty()) {
            break;
        }
    }

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