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
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <set>
#include <cmath>
#include <string>
#include <map>
#include <cassert>
#include <functional>
#include <tuple>
#include <numeric>
#include <queue>
#include <list>

using namespace std;

#define DEBUG 0
#define PII pair<int,int>
#define TIII tuple<int, int, int>
#define MAXN 100010

int V[3], res[MAXN],bottles=3;
set<TIII > stateVisited;

struct BottlesState {
    int v[3], steps;
    BottlesState (int a, int b, int c, int s): steps(s) {
        v[0] = a; v[1] = b; v[2] = c;
    }
    TIII get_tuple(){
        return TIII(this->v[0], this->v[1], this->v[2]);
    }
};
queue<BottlesState> q;

bool try_add_bottle_state (BottlesState bs){
    if (stateVisited.find(bs.get_tuple()) == stateVisited.end()){
        stateVisited.insert(bs.get_tuple());
        q.push(bs);
        return true;
    }
    return false;
}

void exchange_bottles (BottlesState bs, int left, int right){
    // LEFT -> RIGHT
    int volume_transferred = min(V[right] - bs.v[right], bs.v[left]);
    BottlesState leftState = bs;
    leftState.v[left] = bs.v[left] - volume_transferred;
    leftState.v[right] = bs.v[right] + volume_transferred;
    leftState.steps = bs.steps+1;
    try_add_bottle_state(leftState);

    // LEFT <- RIGHT
    volume_transferred = min(V[left] - bs.v[left], bs.v[right]);
    BottlesState rightState = bs;
    rightState.v[left] = bs.v[left] + volume_transferred;
    rightState.v[right] = bs.v[right] - volume_transferred;
    rightState.steps = bs.steps+1;
    try_add_bottle_state(rightState);
}

int main() {
    int a,b,c;
    scanf("%d%d%d%d%d%d", &V[0], &V[1], &V[2], &a, &b, &c);

    for (int i=0; i<=V[2]; ++i)
        res[i]=-1;
    
    try_add_bottle_state(BottlesState(a,b,c,0));

    while (!q.empty()){
        BottlesState bottleState = q.front();
        q.pop();

        for (int i=0; i<bottles; ++i){
            if (res[bottleState.v[i]] == -1){
                res[bottleState.v[i]] = bottleState.steps;
            }
        }

        exchange_bottles(bottleState, 0, 1);
        exchange_bottles(bottleState, 0, 2);
        exchange_bottles(bottleState, 1, 2);
    }

    for (int i=0; i<=V[2]; ++i)
        printf("%d ", res[i]);
    return 0;
}