/* Zadanie: Butelki Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; const int MAXN = 1e5 + 7; const int INF = 1000*1000*1000 + 7; int ans[MAXN]; map<ll, bool> vis; int A, B, C; void solve(int a, int b, int c, int i) { queue<tuple<int, int, int, int>> Q; Q.push({a, b, c, 0}); while (!Q.empty()) { auto [a, b, c, dist] = Q.front(); Q.pop(); ll h = (ll)a + (ll)100001*b + (ll)100001*100001*c; if (vis[h]) continue; vis[h] = true; ans[a] = min(ans[a], dist); ans[b] = min(ans[b], dist); ans[c] = min(ans[c], dist); int ab = min(a, B - b); if (ab > 0) Q.push({a - ab, b + ab, c, dist + 1}); int ba = min(b, A - a); if (ba > 0) Q.push({a + ba, b - ba, c, dist + 1}); int ac = min(a, C - c); if (ac > 0) Q.push({a - ac, b, c + ac, dist + 1}); int ca = min(c, A - a); if (ca > 0) Q.push({a + ca, b, c - ca, dist + 1}); int bc = min(b, C - c); if (bc > 0) Q.push({a, b - bc, c + bc, dist + 1}); int cb = min(c, B - b); if (cb > 0) Q.push({a, b + cb, c - cb, dist + 1}); } } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> A >> B >> C; int a, b, c; cin >> a >> b >> c; for (int i = 0; i <= C; ++i) ans[i] = INT_MAX; solve(a, b, c, 0); for (int i = 0; i <= C; ++i) { if (ans[i] == INT_MAX) cout << "-1 "; else cout << ans[i] << ' '; } cout << '\n'; 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 | /* Zadanie: Butelki Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; const int MAXN = 1e5 + 7; const int INF = 1000*1000*1000 + 7; int ans[MAXN]; map<ll, bool> vis; int A, B, C; void solve(int a, int b, int c, int i) { queue<tuple<int, int, int, int>> Q; Q.push({a, b, c, 0}); while (!Q.empty()) { auto [a, b, c, dist] = Q.front(); Q.pop(); ll h = (ll)a + (ll)100001*b + (ll)100001*100001*c; if (vis[h]) continue; vis[h] = true; ans[a] = min(ans[a], dist); ans[b] = min(ans[b], dist); ans[c] = min(ans[c], dist); int ab = min(a, B - b); if (ab > 0) Q.push({a - ab, b + ab, c, dist + 1}); int ba = min(b, A - a); if (ba > 0) Q.push({a + ba, b - ba, c, dist + 1}); int ac = min(a, C - c); if (ac > 0) Q.push({a - ac, b, c + ac, dist + 1}); int ca = min(c, A - a); if (ca > 0) Q.push({a + ca, b, c - ca, dist + 1}); int bc = min(b, C - c); if (bc > 0) Q.push({a, b - bc, c + bc, dist + 1}); int cb = min(c, B - b); if (cb > 0) Q.push({a, b + cb, c - cb, dist + 1}); } } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> A >> B >> C; int a, b, c; cin >> a >> b >> c; for (int i = 0; i <= C; ++i) ans[i] = INT_MAX; solve(a, b, c, 0); for (int i = 0; i <= C; ++i) { if (ans[i] == INT_MAX) cout << "-1 "; else cout << ans[i] << ' '; } cout << '\n'; return 0; } |