Cod sursa(job #2773222)

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


std::vector<int> results;

std::ifstream in;
std::ofstream out;
std::ofstream out2("../out2.txt");

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 (state < UP_TO) {
            test_bk(state + 1, numbers);
        }

        if (state == UP_TO) {
            for (const auto &itemt: results) {
                out2 << itemt << " ";
            }
            out2 << '\t' << getSum() << '\n';
            printSolution();
        }

        if (getSum() >= target) {
            auto ind = results.begin() + state;
            results.erase(ind, results.end());
            results.resize(6);
            break;
        }
    }
}


int fors(std::vector<int> &numbers, int target_sum) {
    int start_lim = numbers[0];
    int end_lim = numbers[numbers.size() - 1];
    {
        int aux = start_lim;
        if (start_lim > end_lim) {
            start_lim = end_lim;
            end_lim = aux;
        }
    }

    for (const auto &item1: numbers) {
        int sum1 = item1;
        if (sum1 > target_sum) {
            continue;
        }

        {
            int left_iterations = 5;
            int left_sum = target_sum - sum1;
            int max = left_iterations * end_lim;
            int min = left_iterations * start_lim;
            if (left_sum < min || left_sum > max)
                continue;
        }

        for (const auto &item2: numbers) {
            int sum2 = sum1 + item2;
            if (sum2 > target_sum) {
                continue;
            }
            {
                int left_iterations = 4;
                int left_sum = target_sum - sum2;
                int max = left_iterations * end_lim;
                int min = left_iterations * start_lim;
                if (left_sum < min || left_sum > max)
                    continue;
            }
            for (const auto &item3: numbers) {
                int sum3 = sum2 + item3;
                if (sum3 > target_sum) {
                    continue;
                }
                {
                    int left_iterations = 3;
                    int left_sum = target_sum - sum3;
                    int max = left_iterations * end_lim;
                    int min = left_iterations * start_lim;
                    if (left_sum < min || left_sum > max)
                        continue;
                }
                for (const auto &item4: numbers) {
                    int sum4 = sum3 + item4;
                    if (sum4 > target_sum) {
                        continue;
                    }
                    {
                        int left_iterations = 2;
                        int left_sum = target_sum - sum4;
                        int max = left_iterations * end_lim;
                        int min = left_iterations * start_lim;
                        if (left_sum < min || left_sum > max)
                            continue;
                    }
                    for (const auto &item5: numbers) {
                        int sum5 = sum4 + item5;
                        if (sum5 > target_sum) {
                            continue;
                        }
                        {
                            int left_iterations = 1;
                            int left_sum = target_sum - sum5;
                            int max = left_iterations * end_lim;
                            int min = left_iterations * start_lim;
                            if (left_sum < min || left_sum > max)
                                continue;
                        }
                        for (const auto &item6: numbers) {
                            int sum6 = sum5 + item6;
                            if (sum6 > target_sum) {
                                continue;
                            }
                            if (sum6 == target_sum) {
                                out << item1 << " "
                                    << item2 << " "
                                    << item3 << " "
                                    << item4 << " "
                                    << item5 << " "
                                    << item6;
                                return 1;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

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);
    int success = fors(numbers, target_sum);
    if(!success){
        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;
}