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
#include <bits/stdc++.h>

using namespace std;

const size_t BOTTLES = 3;
struct State
{
  array<int, BOTTLES> bottles;
};

struct TestCase
{
  State max;
  State initial;
};

TestCase read_test_case();
void solve_test_case(const TestCase&);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve_test_case(read_test_case());
}

istream& operator>>(istream& stream, State& s)
{
  for (auto& b : s.bottles) stream >> b;
  return stream;
}

TestCase read_test_case()
{
  TestCase tc;
  cin >> tc.max >> tc.initial;
  return tc;
}

bool operator<(const State& lhs, const State& rhs)
{
  return lhs.bottles < rhs.bottles;
}

vector<State> get_neighbors(const State& s, const State& max)
{
  vector<State> result;
  for (size_t from = 0; from < BOTTLES; from++)
    for (size_t to = 0; to < BOTTLES; to++)
    {
      auto amount = min(s.bottles[from], max.bottles[to] - s.bottles[to]);
      auto s2 = s;
      s2.bottles[from] -= amount;
      s2.bottles[to] += amount;
      result.push_back(s2);
    }

  return result;
}

void solve_test_case(const TestCase& tc)
{
  map<State, bool> visited;
  queue<pair<State, size_t>> queue;
  visited[tc.initial] = true;
  queue.push({tc.initial, 0});
  vector<int> result(tc.max.bottles[2] + 1, -1);

  while (!queue.empty())
  {
    auto [state, time] = queue.front();
    queue.pop();
    for (auto b : state.bottles)
      if (result[b] == -1) result[b] = time;

    for (auto n : get_neighbors(state, tc.max))
    {
      if (visited[n]) continue;
      visited[n] = true;
      queue.push({n, time + 1});
    }
  }
  for (auto r : result) cout << r << " ";
  cout << "\n";
}