#include <map> #include <cstdio> const int max_c = 100010; const int max_val = 1000001000; int DP[max_c]; std::map<long long, int> D; int sp, st; long long queue[2000000]; inline void maybe_add(long long a, long long b, long long c, int dist) { long long state = a | (b<<17) | (c<<34); std::map<long long, int>::iterator it = D.find(state); if (it != D.end()) { return; } D[state] = dist; queue[sp++] = state; if (DP[a] > dist) DP[a] = dist; if (DP[b] > dist) DP[b] = dist; if (DP[c] > dist) DP[c] = dist; } int main() { long long A, B, C; long long a, b, c; scanf("%lld %lld %lld", &A, &B, &C); scanf("%lld %lld %lld", &a, &b, &c); for (int i = 0; i <= C; ++i) DP[i] = max_val; DP[a] = DP[b] = DP[c] = 0; long long state = a | (b<<17) | (c<<34); D[state] = 0; st = 0, sp = 1; queue[0] = state; while (st < sp) { state = queue[st++]; a = state & ((1<<17) - 1); b = (state >> 17) & ((1<<17) - 1); c = (state >> 34); int dist = D[state]; long long aa, bb, cc; // Move a -> b if (a + b > B) { bb = B; aa = a + b - B; } else { aa = 0; bb = a + b; } maybe_add(aa, bb, c, dist + 1); // Move a -> c if (a + c > C) { cc = C; aa = a + c - C; } else { aa = 0; cc = a + c; } maybe_add(aa, b, cc, dist + 1); // Move b -> a if (b + a > A) { aa = A; bb = a + b - A; } else { bb = 0; aa = a + b; } maybe_add(aa, bb, c, dist + 1); // Move b -> c if (b + c > C) { cc = C; bb = b + c - C; } else { bb = 0; cc = b + c; } maybe_add(a, bb, cc, dist + 1); // Move c -> a if (a + c > A) { aa = A; cc = a + c - A; } else { cc = 0; aa = a + c; } maybe_add(aa, b, cc, dist + 1); // Move c -> b if (b + c > B) { bb = B; cc = b + c - B; } else { cc = 0; bb = b + c; } maybe_add(a, bb, cc, dist + 1); } for (int i = 0; i<= C; ++i) printf("%d ", DP[i] == max_val ? -1 : DP[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 | #include <map> #include <cstdio> const int max_c = 100010; const int max_val = 1000001000; int DP[max_c]; std::map<long long, int> D; int sp, st; long long queue[2000000]; inline void maybe_add(long long a, long long b, long long c, int dist) { long long state = a | (b<<17) | (c<<34); std::map<long long, int>::iterator it = D.find(state); if (it != D.end()) { return; } D[state] = dist; queue[sp++] = state; if (DP[a] > dist) DP[a] = dist; if (DP[b] > dist) DP[b] = dist; if (DP[c] > dist) DP[c] = dist; } int main() { long long A, B, C; long long a, b, c; scanf("%lld %lld %lld", &A, &B, &C); scanf("%lld %lld %lld", &a, &b, &c); for (int i = 0; i <= C; ++i) DP[i] = max_val; DP[a] = DP[b] = DP[c] = 0; long long state = a | (b<<17) | (c<<34); D[state] = 0; st = 0, sp = 1; queue[0] = state; while (st < sp) { state = queue[st++]; a = state & ((1<<17) - 1); b = (state >> 17) & ((1<<17) - 1); c = (state >> 34); int dist = D[state]; long long aa, bb, cc; // Move a -> b if (a + b > B) { bb = B; aa = a + b - B; } else { aa = 0; bb = a + b; } maybe_add(aa, bb, c, dist + 1); // Move a -> c if (a + c > C) { cc = C; aa = a + c - C; } else { aa = 0; cc = a + c; } maybe_add(aa, b, cc, dist + 1); // Move b -> a if (b + a > A) { aa = A; bb = a + b - A; } else { bb = 0; aa = a + b; } maybe_add(aa, bb, c, dist + 1); // Move b -> c if (b + c > C) { cc = C; bb = b + c - C; } else { bb = 0; cc = b + c; } maybe_add(a, bb, cc, dist + 1); // Move c -> a if (a + c > A) { aa = A; cc = a + c - A; } else { cc = 0; aa = a + c; } maybe_add(aa, b, cc, dist + 1); // Move c -> b if (b + c > B) { bb = B; cc = b + c - B; } else { cc = 0; bb = b + c; } maybe_add(a, bb, cc, dist + 1); } for (int i = 0; i<= C; ++i) printf("%d ", DP[i] == max_val ? -1 : DP[i]); return 0; } |