#include <iostream> #include <vector> #include <algorithm> #include <queue> #define lli long long int using namespace std; struct sssss { int ile, a, b, c; }; const lli mod = 185916617, mn1 = 15917969, mn2 = 2957395639183; int d, e, w, n, m, q, A, B, C; int p, l, k; int wyn[100001]; bool czy[185916617]; queue <sssss> kol; void brucior(int ile, int a, int b, int c) { lli lll; wyn[a] = min(wyn[a], ile); wyn[b] = min(wyn[b], ile); wyn[c] = min(wyn[c], ile); // lll = + 100001ll * () + 10000200001ll * (); if (a) { lll = ((lli)a - min(a, B - b) + mn1 * ((lli)b + min(a, B - b)) + mn2 * c) % mod; if (!czy[lll]) { kol.push({ ile + 1, a - min(a, B - b), b + min(a, B - b), c }); czy[lll] = 1; } //brucior(a - min(a, B - b), b + min(a, B - b), c, ile + 1); lll = ((lli)a - min(a, C - c) + mn1 * b + mn2 * ((lli)c + min(a, C - c))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a - min(a, C - c), b, c + min(a, C - c) }); czy[lll] = 1; } //brucior(a - min(a, C - c), b, c + min(a, C - c), ile + 1); } if (b) { lll = ((lli)a + min(b, A - a) + mn1 * ((lli)b - min(b, A - a)) + mn2 * c) % mod; if (!czy[lll]) { kol.push({ ile + 1, a + min(b, A - a), b - min(b, A - a), c }); czy[lll] = 1; } //brucior(a + min(b, A - a), b - min(b, A - a), c, ile + 1); lll = (a + mn1 * ((lli)b - min(b, C - c)) + mn2 * ((lli)c + min(b, C - c))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a, b - min(b, C - c), c + min(b, C - c) }); czy[lll] = 1; } //brucior(a, b - min(b, C - c), c + min(b, C - c), ile + 1); } if (c) { lll = (a + mn1 * ((lli)b + min(c, B - b)) + mn2 * ((lli)c - min(c, B - b))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a, b + min(c, B - b), c - min(c, B - b) }); czy[lll] = 1; } //brucior(a, b + min(c, B - b), c - min(c, B - b), ile + 1); lll = ((lli)a + min(c, A - a) + mn1 * b + mn2 * ((lli)c - min(c, A - a))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a + min(c, A - a), b, c - min(c, A - a) }); czy[lll] = 1; } //brucior(a + min(c, A - a), b, c - min(c, A - a), ile + 1); } } int main() { fill(wyn, wyn + 100000, 2000000000); scanf("%d%d%d", &A, &B, &C); scanf("%d%d%d", &l, &k, &p); kol.push({ 1, l, k, p }); czy[((lli)l + mn1 * k + mn2 * p) % mod] = 1; while (!kol.empty()) { brucior(kol.front().ile, kol.front().a, kol.front().b, kol.front().c); kol.pop(); } for (d = 0; d <= C; ++d) { if (wyn[d] == 2000000000) { printf("-1 "); } else { printf("%d ", wyn[d] - 1); } } }
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 <iostream> #include <vector> #include <algorithm> #include <queue> #define lli long long int using namespace std; struct sssss { int ile, a, b, c; }; const lli mod = 185916617, mn1 = 15917969, mn2 = 2957395639183; int d, e, w, n, m, q, A, B, C; int p, l, k; int wyn[100001]; bool czy[185916617]; queue <sssss> kol; void brucior(int ile, int a, int b, int c) { lli lll; wyn[a] = min(wyn[a], ile); wyn[b] = min(wyn[b], ile); wyn[c] = min(wyn[c], ile); // lll = + 100001ll * () + 10000200001ll * (); if (a) { lll = ((lli)a - min(a, B - b) + mn1 * ((lli)b + min(a, B - b)) + mn2 * c) % mod; if (!czy[lll]) { kol.push({ ile + 1, a - min(a, B - b), b + min(a, B - b), c }); czy[lll] = 1; } //brucior(a - min(a, B - b), b + min(a, B - b), c, ile + 1); lll = ((lli)a - min(a, C - c) + mn1 * b + mn2 * ((lli)c + min(a, C - c))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a - min(a, C - c), b, c + min(a, C - c) }); czy[lll] = 1; } //brucior(a - min(a, C - c), b, c + min(a, C - c), ile + 1); } if (b) { lll = ((lli)a + min(b, A - a) + mn1 * ((lli)b - min(b, A - a)) + mn2 * c) % mod; if (!czy[lll]) { kol.push({ ile + 1, a + min(b, A - a), b - min(b, A - a), c }); czy[lll] = 1; } //brucior(a + min(b, A - a), b - min(b, A - a), c, ile + 1); lll = (a + mn1 * ((lli)b - min(b, C - c)) + mn2 * ((lli)c + min(b, C - c))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a, b - min(b, C - c), c + min(b, C - c) }); czy[lll] = 1; } //brucior(a, b - min(b, C - c), c + min(b, C - c), ile + 1); } if (c) { lll = (a + mn1 * ((lli)b + min(c, B - b)) + mn2 * ((lli)c - min(c, B - b))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a, b + min(c, B - b), c - min(c, B - b) }); czy[lll] = 1; } //brucior(a, b + min(c, B - b), c - min(c, B - b), ile + 1); lll = ((lli)a + min(c, A - a) + mn1 * b + mn2 * ((lli)c - min(c, A - a))) % mod; if (!czy[lll]) { kol.push({ ile + 1, a + min(c, A - a), b, c - min(c, A - a) }); czy[lll] = 1; } //brucior(a + min(c, A - a), b, c - min(c, A - a), ile + 1); } } int main() { fill(wyn, wyn + 100000, 2000000000); scanf("%d%d%d", &A, &B, &C); scanf("%d%d%d", &l, &k, &p); kol.push({ 1, l, k, p }); czy[((lli)l + mn1 * k + mn2 * p) % mod] = 1; while (!kol.empty()) { brucior(kol.front().ile, kol.front().a, kol.front().b, kol.front().c); kol.pop(); } for (d = 0; d <= C; ++d) { if (wyn[d] == 2000000000) { printf("-1 "); } else { printf("%d ", wyn[d] - 1); } } } |