Cod sursa(job #3131921)

Utilizator LazarDanielGabrielLazar Daniel-Gabriel LazarDanielGabriel Data 21 mai 2023 21:29:26
Problema Loto Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> ticket;
bool found = false;

void generate_ticket(const vector<int>& numbers, int current_sum, int target_sum, int index) {
    if (ticket.size() == 6 && current_sum == target_sum) {
        found = true;
        return;
    }
    if (current_sum > target_sum || index >= numbers.size() || ticket.size() > 6) {
        return;
    }
    for (int i = index; i < numbers.size() && !found; i++) {
        ticket.push_back(numbers[i]);
        generate_ticket(numbers, current_sum + numbers[i], target_sum, i);
        ticket.pop_back();
    }
}

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

    int N, S;
    fin >> N >> S;

    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        fin >> numbers[i];
    }
    fin.close();

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

    generate_ticket(numbers, 0, S, 0);

    if (found) {
        for (int i = 0; i < 6; i++) {
            fout << ticket[i] << " ";
        }
        fout << "\n";
    } else {
        fout << "-1\n";
    }

    fout.close();

    return 0;
}