#include <iostream> #include <vector> #include <unordered_map> #include <queue> using namespace std; int A, B, C; typedef tuple<int, int> Para; typedef tuple<int, int, int> Stan; struct MyHash { std::size_t operator()(Stan const& stan) const noexcept { auto [a, b, c] = stan; hash<int> hash_int; std::size_t h1 = hash_int(a); std::size_t h2 = hash_int(b); std::size_t h3 = hash_int(c); return h1 + h2 * 33575887 + h3 * 95289059; } }; Para przelej_lewy_do_prawego(int lewy, int prawy, int max_prawy) { int do_przelania = min(lewy, max_prawy - prawy); if (do_przelania <= 0) { return {-1, -1}; } return {lewy - do_przelania, prawy + do_przelania}; } vector<Stan> przelewaj(Stan stan) { auto [a, b, c] = stan; vector<Stan> nowe; int l, p; tie(l, p) = przelej_lewy_do_prawego(a, b, B); if (l >= 0) nowe.push_back({l, p, c}); tie(l, p) = przelej_lewy_do_prawego(a, c, C); if (l >= 0) nowe.push_back({l, b, p}); tie(l, p) = przelej_lewy_do_prawego(b, a, A); if (l >= 0) nowe.push_back({p, l, c}); tie(l, p) = przelej_lewy_do_prawego(b, c, C); if (l >= 0) nowe.push_back({a, l, p}); tie(l, p) = przelej_lewy_do_prawego(c, a, A); if (l >= 0) nowe.push_back({p, b, l}); tie(l, p) = przelej_lewy_do_prawego(c, b, B); if (l >= 0) nowe.push_back({a, p, l}); return nowe; } int main() { ios_base::sync_with_stdio(0); int a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; unordered_map<Stan, int, MyHash> stany = {}; deque<tuple<Stan, int>> kolejka; Stan stan0 = {a, b, c}; stany[stan0] = 0; kolejka.push_back({stan0, 0}); while (!kolejka.empty()) { Stan stan; int kroki; tie(stan, kroki) = kolejka.front(); kolejka.pop_front(); auto nowe_stany = przelewaj(stan); for (Stan nowy_stan: nowe_stany) { if (stany.find(nowy_stan) == stany.end()) { stany[nowy_stan] = kroki + 1; kolejka.push_back({nowy_stan, kroki + 1}); } } } vector<int> osiagalne(C + 1, -1); auto aktualizuj_osiag = [&osiagalne](int poziom, int kroki) { if (osiagalne[poziom] < 0) { osiagalne[poziom] = kroki; } else { osiagalne[poziom] = min(osiagalne[poziom], kroki); } }; for (const auto & [stan, kroki]: stany) { auto [a, b, c] = stan; aktualizuj_osiag(a, kroki); aktualizuj_osiag(b, kroki); aktualizuj_osiag(c, kroki); } for (int k = 0; k <= C; ++k) { cout << osiagalne[k] << ' '; } cout << endl; return 0; }
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 100 101 102 103 104 105 106 107 108 | #include <iostream> #include <vector> #include <unordered_map> #include <queue> using namespace std; int A, B, C; typedef tuple<int, int> Para; typedef tuple<int, int, int> Stan; struct MyHash { std::size_t operator()(Stan const& stan) const noexcept { auto [a, b, c] = stan; hash<int> hash_int; std::size_t h1 = hash_int(a); std::size_t h2 = hash_int(b); std::size_t h3 = hash_int(c); return h1 + h2 * 33575887 + h3 * 95289059; } }; Para przelej_lewy_do_prawego(int lewy, int prawy, int max_prawy) { int do_przelania = min(lewy, max_prawy - prawy); if (do_przelania <= 0) { return {-1, -1}; } return {lewy - do_przelania, prawy + do_przelania}; } vector<Stan> przelewaj(Stan stan) { auto [a, b, c] = stan; vector<Stan> nowe; int l, p; tie(l, p) = przelej_lewy_do_prawego(a, b, B); if (l >= 0) nowe.push_back({l, p, c}); tie(l, p) = przelej_lewy_do_prawego(a, c, C); if (l >= 0) nowe.push_back({l, b, p}); tie(l, p) = przelej_lewy_do_prawego(b, a, A); if (l >= 0) nowe.push_back({p, l, c}); tie(l, p) = przelej_lewy_do_prawego(b, c, C); if (l >= 0) nowe.push_back({a, l, p}); tie(l, p) = przelej_lewy_do_prawego(c, a, A); if (l >= 0) nowe.push_back({p, b, l}); tie(l, p) = przelej_lewy_do_prawego(c, b, B); if (l >= 0) nowe.push_back({a, p, l}); return nowe; } int main() { ios_base::sync_with_stdio(0); int a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; unordered_map<Stan, int, MyHash> stany = {}; deque<tuple<Stan, int>> kolejka; Stan stan0 = {a, b, c}; stany[stan0] = 0; kolejka.push_back({stan0, 0}); while (!kolejka.empty()) { Stan stan; int kroki; tie(stan, kroki) = kolejka.front(); kolejka.pop_front(); auto nowe_stany = przelewaj(stan); for (Stan nowy_stan: nowe_stany) { if (stany.find(nowy_stan) == stany.end()) { stany[nowy_stan] = kroki + 1; kolejka.push_back({nowy_stan, kroki + 1}); } } } vector<int> osiagalne(C + 1, -1); auto aktualizuj_osiag = [&osiagalne](int poziom, int kroki) { if (osiagalne[poziom] < 0) { osiagalne[poziom] = kroki; } else { osiagalne[poziom] = min(osiagalne[poziom], kroki); } }; for (const auto & [stan, kroki]: stany) { auto [a, b, c] = stan; aktualizuj_osiag(a, kroki); aktualizuj_osiag(b, kroki); aktualizuj_osiag(c, kroki); } for (int k = 0; k <= C; ++k) { cout << osiagalne[k] << ' '; } cout << endl; return 0; } |