Cod sursa(job #2915685)

Utilizator alin.gabrielAlin Gabriel Arhip alin.gabriel Data 24 iulie 2022 07:26:22
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
using namespace std;

ofstream fout("loto.out");

vector<int> sol, v;
long long ts = 0, s;
int n, cmax = 0;

void print_sol() {
    for (int i = 0; i < 5 ; i++)
        fout << sol[i] << " ";
    fout << sol[sol.size() - 1];
    fout.close();
    exit(0);
}

bool found_sol() {
    return ts == s && sol.size() == 6;
}

void backtrack() {
    ts -= sol[sol.size() - 1];
    sol.pop_back();
}

void btk(int idx) {
    if (found_sol())
        print_sol();

    if (sol.size() >= 6)
        return;

    for (int i = idx; i < n ; i++) {
        if (ts + v[i] <= s && sol.size() < 6) {
            if (sol.size() == 4 && cmax < s - ts - v[i])
                continue;
            sol.push_back(v[i]);
            ts += v[i];
            btk(i);
            backtrack();
        }
    }

}

vector<int> qsort(vector<int> vv) {
    int piv = vv.size() / 2;
    vector<int> l;
    vector<int> h;

    if (vv.size() == 1)
        return vv;

    for (int e : vv) {
        if (e < vv[piv])
            l.push_back(e);
        else 
            h.push_back(e);
    }

    vector<int> buf = qsort(l);
    for (int e: qsort(h))
        buf.push_back(e);
    return buf;
}


int main() {
    ifstream fin("loto.in");

    fin >> n;
    fin >> s;
    int tmp;
    for (int i = 0 ; i < n; i++) {
        fin >> tmp;
        if (tmp > cmax) 
            cmax = tmp;
        v.push_back(tmp);
    }
    fin.close();

    v = qsort(v);
    btk(0);

    fout << -1;
    fout.close();
    return 0;
}