#include <iostream> #include <queue> #include <unordered_set> #include <climits> template<> struct std::hash<std::pair<int, int>> { std::size_t operator()(const std::pair<int, int> &d) const { std::size_t ha = std::hash<int>{}(d.first); std::size_t hb = std::hash<int>{}(d.second); return ha ^ (hb << 1); } }; int main() { int A, B, C, a, b, c; std::cin >> A >> B >> C >> a >> b >> c; int sum = a + b + c; std::queue<std::tuple<int, int, int>> queue; queue.emplace(a, b, 0); std::unordered_set<std::pair<int, int>> done; done.emplace(a, b); std::vector<int> best(C + 1, INT_MAX); while(!queue.empty()) { auto [a_, b_, i] = queue.front(); queue.pop(); int c_ = sum - (a_ + b_); if (best[a_] > i) { best[a_] = i; } if (best[b_] > i) { best[b_] = i; } if (best[c_] > i) { best[c_] = i; } std::vector<std::pair<int, int>> add; if (a_ > 0) { int badd = std::min(a_, B - b_); add.emplace_back(a_ - badd, b_ + badd); int cadd = std::min(a_, C - c_); add.emplace_back(a_ - cadd, b_); } if (b_ > 0) { int aadd = std::min(b_, A - a_); add.emplace_back(a_ + aadd, b_ - aadd); int cadd = std::min(b_, C - c_); add.emplace_back(a_, b_ - cadd); } if (c_ > 0) { int aadd = std::min(c_, A - a_); add.emplace_back(a_ + aadd, b_); int badd = std::min(c_, B - b_); add.emplace_back(a_, b_ + badd); } for (auto added: add) { if (done.count(added) == 0) { done.insert(added); queue.emplace(added.first, added.second, i + 1); } } } for (int i = 0; i <= C; ++i) { std::cout << (best[i] < INT_MAX ? best[i] : -1) << " "; } std::cout << "\n"; }
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 | #include <iostream> #include <queue> #include <unordered_set> #include <climits> template<> struct std::hash<std::pair<int, int>> { std::size_t operator()(const std::pair<int, int> &d) const { std::size_t ha = std::hash<int>{}(d.first); std::size_t hb = std::hash<int>{}(d.second); return ha ^ (hb << 1); } }; int main() { int A, B, C, a, b, c; std::cin >> A >> B >> C >> a >> b >> c; int sum = a + b + c; std::queue<std::tuple<int, int, int>> queue; queue.emplace(a, b, 0); std::unordered_set<std::pair<int, int>> done; done.emplace(a, b); std::vector<int> best(C + 1, INT_MAX); while(!queue.empty()) { auto [a_, b_, i] = queue.front(); queue.pop(); int c_ = sum - (a_ + b_); if (best[a_] > i) { best[a_] = i; } if (best[b_] > i) { best[b_] = i; } if (best[c_] > i) { best[c_] = i; } std::vector<std::pair<int, int>> add; if (a_ > 0) { int badd = std::min(a_, B - b_); add.emplace_back(a_ - badd, b_ + badd); int cadd = std::min(a_, C - c_); add.emplace_back(a_ - cadd, b_); } if (b_ > 0) { int aadd = std::min(b_, A - a_); add.emplace_back(a_ + aadd, b_ - aadd); int cadd = std::min(b_, C - c_); add.emplace_back(a_, b_ - cadd); } if (c_ > 0) { int aadd = std::min(c_, A - a_); add.emplace_back(a_ + aadd, b_); int badd = std::min(c_, B - b_); add.emplace_back(a_, b_ + badd); } for (auto added: add) { if (done.count(added) == 0) { done.insert(added); queue.emplace(added.first, added.second, i + 1); } } } for (int i = 0; i <= C; ++i) { std::cout << (best[i] < INT_MAX ? best[i] : -1) << " "; } std::cout << "\n"; } |