#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e5 + 7; struct state { int a, b, c; bool operator<(const state &o) const { if (a < o.a) return 1; if (a == o.a && b < o.b) return 1; if (a == o.a && b == o.b && c < o.c) return 1; return 0; } }; int a, b, c, A, B, C; int t[NMAX]; set<state> vis; void bfs() { queue<state> q; q.push({a, b, c}); vis.insert({a, b, c}); int tura = 0, size = 1, cnt = 0; while (!q.empty()) { state s = q.front(); q.pop(); if (t[s.a] == -1) { t[s.a] = tura; } if (t[s.b] == -1) { t[s.b] = tura; } if (t[s.c] == -1) { t[s.c] = tura; } // a->b if (s.a + s.b <= B) { if (vis.count({0, s.a + s.b, s.c}) == 0) { vis.insert({0, s.a + s.b, s.c}); q.push({0, s.a + s.b, s.c}); } } else { if (vis.count({s.a + s.b - B, B, s.c}) == 0) { vis.insert({s.a + s.b - B, B, s.c}); q.push({s.a + s.b - B, B, s.c}); } } // a->c if (s.a + s.c <= C) { if (vis.count({0, s.b, s.a + s.c}) == 0) { vis.insert({0, s.b, s.a + s.c}); q.push({0, s.b, s.a + s.c}); } } else { if (vis.count({s.a + s.c - C, s.b, C}) == 0) { vis.insert({s.a + s.c - C, s.b, C}); q.push({s.a + s.c - C, s.b, C}); } } // b->c if (s.b + s.c <= C) { if (vis.count({s.a, 0, s.b + s.c}) == 0) { vis.insert({s.a, 0, s.b + s.c}); q.push({s.a, 0, s.b + s.c}); } } else { if (vis.count({s.a, s.b + s.c - C, C}) == 0) { vis.insert({s.a, s.b + s.c - C, C}); q.push({s.a, s.b + s.c - C, C}); } } // b->a if (s.a + s.b <= A) { if (vis.count({s.a + s.b, 0, s.c}) == 0) { vis.insert({s.a + s.b, 0, s.c}); q.push({s.a + s.b, 0, s.c}); } } else { if (vis.count({A, s.a + s.b - A, s.c}) == 0) { vis.insert({A, s.a + s.b - A, s.c}); q.push({A, s.a + s.b - A, s.c}); } } // c->a if (s.a + s.c <= A) { if (vis.count({s.a + s.c, s.b, 0}) == 0) { vis.insert({s.a + s.c, s.b, 0}); q.push({s.a + s.c, s.b, 0}); } } else { if (vis.count({A, s.b, s.a + s.c - A}) == 0) { vis.insert({A, s.b, s.a + s.c - A}); q.push({A, s.b, s.a + s.c - A}); } } // c->b if (s.b + s.c <= B) { if (vis.count({s.a, s.b + s.c, 0}) == 0) { vis.insert({s.a, s.b + s.c, 0}); q.push({s.a, s.b + s.c, 0}); } } else { if (vis.count({s.a, B, s.b + s.c - B}) == 0) { vis.insert({s.a, B, s.b + s.c - B}); q.push({s.a, B, s.b + s.c - B}); } } cnt++; if (cnt == size) { cnt = 0; tura++; size = q.size(); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> A >> B >> C >> a >> b >> c; for (int i = 0; i <= C; ++i) { t[i] = -1; } bfs(); for (int i = 0; i <= C; ++i) { cout << t[i] << " "; } 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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 1e5 + 7; struct state { int a, b, c; bool operator<(const state &o) const { if (a < o.a) return 1; if (a == o.a && b < o.b) return 1; if (a == o.a && b == o.b && c < o.c) return 1; return 0; } }; int a, b, c, A, B, C; int t[NMAX]; set<state> vis; void bfs() { queue<state> q; q.push({a, b, c}); vis.insert({a, b, c}); int tura = 0, size = 1, cnt = 0; while (!q.empty()) { state s = q.front(); q.pop(); if (t[s.a] == -1) { t[s.a] = tura; } if (t[s.b] == -1) { t[s.b] = tura; } if (t[s.c] == -1) { t[s.c] = tura; } // a->b if (s.a + s.b <= B) { if (vis.count({0, s.a + s.b, s.c}) == 0) { vis.insert({0, s.a + s.b, s.c}); q.push({0, s.a + s.b, s.c}); } } else { if (vis.count({s.a + s.b - B, B, s.c}) == 0) { vis.insert({s.a + s.b - B, B, s.c}); q.push({s.a + s.b - B, B, s.c}); } } // a->c if (s.a + s.c <= C) { if (vis.count({0, s.b, s.a + s.c}) == 0) { vis.insert({0, s.b, s.a + s.c}); q.push({0, s.b, s.a + s.c}); } } else { if (vis.count({s.a + s.c - C, s.b, C}) == 0) { vis.insert({s.a + s.c - C, s.b, C}); q.push({s.a + s.c - C, s.b, C}); } } // b->c if (s.b + s.c <= C) { if (vis.count({s.a, 0, s.b + s.c}) == 0) { vis.insert({s.a, 0, s.b + s.c}); q.push({s.a, 0, s.b + s.c}); } } else { if (vis.count({s.a, s.b + s.c - C, C}) == 0) { vis.insert({s.a, s.b + s.c - C, C}); q.push({s.a, s.b + s.c - C, C}); } } // b->a if (s.a + s.b <= A) { if (vis.count({s.a + s.b, 0, s.c}) == 0) { vis.insert({s.a + s.b, 0, s.c}); q.push({s.a + s.b, 0, s.c}); } } else { if (vis.count({A, s.a + s.b - A, s.c}) == 0) { vis.insert({A, s.a + s.b - A, s.c}); q.push({A, s.a + s.b - A, s.c}); } } // c->a if (s.a + s.c <= A) { if (vis.count({s.a + s.c, s.b, 0}) == 0) { vis.insert({s.a + s.c, s.b, 0}); q.push({s.a + s.c, s.b, 0}); } } else { if (vis.count({A, s.b, s.a + s.c - A}) == 0) { vis.insert({A, s.b, s.a + s.c - A}); q.push({A, s.b, s.a + s.c - A}); } } // c->b if (s.b + s.c <= B) { if (vis.count({s.a, s.b + s.c, 0}) == 0) { vis.insert({s.a, s.b + s.c, 0}); q.push({s.a, s.b + s.c, 0}); } } else { if (vis.count({s.a, B, s.b + s.c - B}) == 0) { vis.insert({s.a, B, s.b + s.c - B}); q.push({s.a, B, s.b + s.c - B}); } } cnt++; if (cnt == size) { cnt = 0; tura++; size = q.size(); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> A >> B >> C >> a >> b >> c; for (int i = 0; i <= C; ++i) { t[i] = -1; } bfs(); for (int i = 0; i <= C; ++i) { cout << t[i] << " "; } return 0; } |