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
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>

using namespace std;

//struct statecomp {
//    bool operator() (const vector<int>& lhs, const vector<int>& rhs) const {
//        return lhs[0] < rhs[0]
//            || (lhs[0] == rhs[0] && lhs[1] < rhs[1])
//            || (lhs[0] == rhs[0] && lhs[1] == rhs[1] && lhs[2] < rhs[2]);
//    }
//};

const int BOTTLES_NUM = 3;

vector<int> sizes(BOTTLES_NUM);
set<vector<int> > states;
int depth = 0;

vector<int> move(vector<int>& state, int from, int to) {
    int spaceLeft = sizes[to] - state[to];
    int newFromAmount = max(0, state[from] - spaceLeft);
    int newToAmount = state[to] + (state[from] - newFromAmount);

    vector<int> newState(state);
    newState[from] = newFromAmount;
    newState[to] = newToAmount;
    return newState;
}

void updateResult(int amount, vector<int>& results) {
    if (results[amount] == -1) {
        results[amount] = depth;
    }
}

void addNewState(vector<int>& newState, vector<vector<int> >& statesToCheck, vector<int>& results) {
    states.insert(newState);
    statesToCheck.push_back(newState);

    updateResult(newState[0], results);
    updateResult(newState[1], results);
    updateResult(newState[2], results);
}

void moveAndUpdate(vector<int>& state, int from, int to, vector<vector<int> >& statesToCheck, vector<int>& results) {
    vector<int> newState = move(state, from, to);
    if (states.find(newState) == states.end()) {
        addNewState(newState, statesToCheck, results);
    }
}

int main() {
    for (int i = 0; i < BOTTLES_NUM; i++) {
        int size;
        scanf("%d", &size);
        sizes[i] = size;
    }

    vector<int> amounts(BOTTLES_NUM);
    for (int i = 0; i < BOTTLES_NUM; i++) {
        int amount;
        scanf("%d", &amount);
        amounts[i] = amount;
    }

    vector<vector<int> > statesToCheck;
    int maxSize = max(sizes[0], max(sizes[1], sizes[2]));
    vector<int> results(maxSize + 1, -1);

    addNewState(amounts, statesToCheck, results);
    depth++;

    while (!statesToCheck.empty()) {
        vector<vector<int> > nextStatesToCheck;
        for (int i = 0; i < statesToCheck.size(); i++) {
            vector<int> stateToCheck = statesToCheck[i];

            moveAndUpdate(stateToCheck, 0, 1, nextStatesToCheck, results);
            moveAndUpdate(stateToCheck, 0, 2, nextStatesToCheck, results);
            moveAndUpdate(stateToCheck, 1, 0, nextStatesToCheck, results);
            moveAndUpdate(stateToCheck, 1, 2, nextStatesToCheck, results);
            moveAndUpdate(stateToCheck, 2, 0, nextStatesToCheck, results);
            moveAndUpdate(stateToCheck, 2, 1, nextStatesToCheck, results);
        }

        statesToCheck = nextStatesToCheck;
        depth++;
    }

    printf("%d", results[0]);
    for (int i = 1; i < maxSize + 1; i++) {
        printf(" %d", results[i]);
    }
    printf("\n");
}