Pagini recente » Cod sursa (job #2798290) | Cod sursa (job #984378) | Cod sursa (job #3196493) | Cod sursa (job #557382) | Cod sursa (job #2773221)
#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::greater<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;
}