Cod sursa(job #3131885)

Utilizator bobic.teona20Bobic Teona-Christiana bobic.teona20 Data 21 mai 2023 20:53:08
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

void find_winning_numbers(int target, const vector<int>& numbers, int start, int end, vector<int>& chosen_numbers, ofstream& output) {
    if (target == 0 && chosen_numbers.size() == 6) {
        for (int num : chosen_numbers) {
            output << num << " ";
        }
        output << endl;
        exit(0);
    }
    if (target < 0 || chosen_numbers.size() == 6 || start > end) {
        return;
    }

    for (int i = start; i <= end; i++) {
        chosen_numbers.push_back(numbers[i]);
        find_winning_numbers(target - numbers[i], numbers, i, end, chosen_numbers, output);
        chosen_numbers.pop_back();
    }
}

int main() {
    ifstream input("loto.in");
    ofstream output("loto.out");

    int N, S;
    input >> N >> S;

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

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

    unordered_map<int, int> sums;

    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            for (int k = j + 1; k < N; k++) {
                int sum = numbers[i] + numbers[j] + numbers[k];
                if (sums.find(sum) == sums.end()) {
                    sums[sum] = i;
                }
            }
        }
    }

    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            for (int k = j + 1; k < N; k++) {
                int target = S - (numbers[i] + numbers[j] + numbers[k]);
                auto it = sums.find(target);
                if (it != sums.end() && it->second != i && it->second != j && it->second != k) {
                    output << numbers[i] << " " << numbers[j] << " " << numbers[k] << " "
                           << numbers[it->second] << " " << numbers[j] << " " << numbers[k] << endl;
                    input.close();
                    output.close();
                    return 0;
                }
            }
        }
    }

    output << -1 << endl;

    input.close();
    output.close();

    return 0;
}