Cod sursa(job #3130181)

Utilizator vatau.lorenaVatau Lorena vatau.lorena Data 16 mai 2023 23:41:39
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Combination {
    long long sum;
    int i1, i2, i3;

    bool operator<(const Combination& other) const {
        return sum < other.sum;
    }
};

void readInput(int& N, long long& S, vector<int>& numbers) {
    ifstream fin("loto.in");
    fin >> N >> S;
    numbers.resize(N);
    for (int i = 0; i < N; i++) {
        fin >> numbers[i];
    }
    fin.close();
}

void writeOutput(const vector<int>& combination) {
    ofstream fout("loto.out");
    if (combination.empty()) {
        fout << -1 << '\n';
    } else {
        for (int i = 0; i < 6; i++) {
            fout << combination[i] << ' ';
        }
        fout << '\n';
    }
    fout.close();
}

vector<int> generateTicket(const vector<int>& numbers, int targetSum) {
    vector<Combination> combinations;
    int N = numbers.size();

    // Generate all possible combinations of 3 numbers
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = j; k < N; k++) {
                long long sum = numbers[i] + numbers[j] + numbers[k];
                combinations.push_back({ sum, i, j, k });
            }
        }
    }

    // Sort the combinations based on the sum
    sort(combinations.begin(), combinations.end());

    // Find a combination that yields the target sum
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = j; k < N; k++) {
                long long remainingSum = targetSum - numbers[i] - numbers[j] - numbers[k];
                Combination targetCombination = { remainingSum, -1, -1, -1 };
                auto it = lower_bound(combinations.begin(), combinations.end(), targetCombination);

                if (it != combinations.end() && it->sum == remainingSum) {
                    return { numbers[i], numbers[j], numbers[k], numbers[it->i1], numbers[it->i2], numbers[it->i3] };
                }
            }
        }
    }

    return {};
}

int main() {
    int N;
    long long S;
    vector<int> numbers;

    readInput(N, S, numbers);
    vector<int> ticket = generateTicket(numbers, S);
    writeOutput(ticket);

    return 0;
}