usaco/holstein.cpp at master · cadaniluk/usaco · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
ID: th3c0r11
TASK: holstein
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <limits>

using namespace std;

int noVitamins;
int noFeeds;
vector<int> requirements;
vector<vector<int>> vitaminsPerFeed;
vector<vector<int>> solutions;
int minSolution = 16;

void tryFeed(int i, vector<int> solution, vector<int> requirements)
{
    solution.push_back(i);

    bool allZero = true;
    for (int j = 0; j < requirements.size(); ++j) {
        requirements[j] -= vitaminsPerFeed[i][j];
        if (requirements[j] > 0)
            allZero = false;
    }

    if (solution.size() >= minSolution)
        return;

    if (allZero) {
        minSolution = solution.size();
        solutions.push_back(solution);
    } else {
        for (int j = i + 1; j < noFeeds; ++j) {
            tryFeed(j, solution, requirements);
        }
    }
}

int main()
{
    ifstream in{"holstein.in"};
    ofstream out{"holstein.out"};

    in >> noVitamins;

    for (int i = 0; i < noVitamins; ++i) {
        int req;
        in >> req;
        requirements.push_back(req);
    }

    in >> noFeeds;

    for (int i = 0; i < noFeeds; ++i) {
        std::vector<int> vitamins;
        for (int j = 0; j < noVitamins; ++j) {
            int amountVitamin;
            in >> amountVitamin;
            vitamins.push_back(amountVitamin);
        }
        vitaminsPerFeed.push_back(move(vitamins));
    }

    for (int i = 0; i < noFeeds; ++i)
        tryFeed(i, {}, requirements);

    auto sol = *std::min_element(solutions.begin(), solutions.end(), [](vector<int>& sol1, vector<int>& sol2) {
        if (sol1.size() != sol2.size())
            return sol1.size() < sol2.size();
        int sum1 = 0, sum2 = 0;
        for (int i : sol1)
            sum1 += i;
        for (int i : sol2)
            sum2 += i;
        return sum1 < sum2;
    });

    out << minSolution << ' ';
    for (int i = 0; i < sol.size() - 1; ++i)
        out << sol[i] + 1 << ' ';
    out << sol[sol.size() - 1] + 1 << '\n';
}