Cod sursa(job #2773153)

Utilizator Gabryel9898Bizdoc Vasile Gabriel Gabryel9898 Data 5 septembrie 2021 02:45:58
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <algorithm>
#include <chrono>
#include <fstream>
#include <vector>


std::vector<int> results;

std::ifstream in;
std::ofstream out;

int target;

const int UP_TO = 5;

int getSum() {
    int sum = 0;
    for (const auto &item: results) {
        sum += item;
    }
    return sum;
}

void printSolution() {
    int sum = getSum();
    if (sum == target) {
        for (const auto &item: results) {
            out << item << " ";
        }
        exit(0);
    }
}

void test_bk(int state, std::vector<int> &numbers) {
    for (const auto &item: numbers) {
        results[state] = item;

        if (getSum() > target) continue;

        if (state == UP_TO)
            printSolution();

        if (state < UP_TO) {
            test_bk(state + 1, numbers);
        }
    }
}


void solve() {
    results.resize(UP_TO + 1);

    in.open("../loto.in");
    out.open("../loto.out");

    int number_of_numbers, target_sum;

    // open file
    int ok = in.is_open() && in.is_open();
    if (!ok) {
        std::cout << "Cant open files!";
        return;
    }
    in >> number_of_numbers >> target_sum;
    target = target_sum;

    std::vector<int> numbers(number_of_numbers);

    for (int &item: numbers) {
        in >> item;
    }

    in.close();
    std::sort(numbers.begin(), numbers.end(), std::less<int>());
    test_bk(0, numbers);
    out << -1;
}


int main() {
    auto start = std::chrono::high_resolution_clock::now();

    solve();

    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    std::cout << std::endl << "[time]:" << duration.count() << std::endl;
    return 0;
}