Cod sursa(job #2915684)

Utilizator alin.gabrielAlin Gabriel Arhip alin.gabriel Data 24 iulie 2022 06:32:03
Problema Loto Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 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();
        }
    }

}

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();

    btk(0);

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