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 <array>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>

using namespace std;

using Butelki = array< int , 3 >;
const int A = 0;
const int B = 1;
const int C = 2;

int main() {
	Butelki pojemnosci;
	cin >> pojemnosci[A] >> pojemnosci[B] >> pojemnosci[C];

	Butelki start;
	cin >> start[A] >> start[B] >> start[C];

	array< pair< int, int >, 6 > przelewy = {{
		{0, 1},
		{0, 2},
		{1, 0},
		{1, 2},
		{2, 0},
		{2, 1}
	}};

	vector< int > odp(pojemnosci[C] + 1, -1);
	int ile = 0;
	odp[start[A]] = ile;
	odp[start[B]] = ile;
	odp[start[C]] = ile;

	set< Butelki > widziane;
	vector< Butelki > aktywne = { start };

	while(aktywne.size() > 0) {
		ile += 1;
		vector< Butelki > nowe;

		for(auto&& akt : aktywne) {
			for (auto&& p : przelewy) {
				int nalewam = p.first;
				int wylewam = p.second;

				int const miejsce = pojemnosci[nalewam] -  akt[nalewam];
				int przelew = min(miejsce, akt[wylewam]);

				if(przelew == 0) continue;

				std::array< int , 2 > poziomy = {
					akt[nalewam] + przelew,
					akt[wylewam] - przelew
				};

				for (int p : poziomy) {
					if(odp[p] == -1) {
						odp[p] = ile;
					}

					Butelki nowa = akt;
					nowa[nalewam] += przelew;
					nowa[wylewam] -= przelew;

					if(widziane.find(nowa) == widziane.end()) {
						nowe.push_back(nowa);
						widziane.insert(nowa);
					}
				}
			}
		}

		aktywne.clear();
		swap(nowe, aktywne);
	}

	cout << odp[0];
	for (int i = 1; i < odp.size(); ++i) {
		cout << " " << odp[i];
	} 
	cout << "\n";
}