#include <iostream> #include <queue> #include <map> #include <utility> using namespace std; int A, B, C; struct my_s { int a, b, c, k; }; const int rozmiar = 1e5 + 5; queue <my_s> q; int butla[rozmiar]; map<pair<pair<int, int>, int>,bool> uzyte; my_s pom; my_s nalewane; int ile_nalac; int main() { for (int i = 0; i < rozmiar; i++) butla[i] = -1; ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; //butla[a] = 0; //butla[b] = 0; //butla[c] = 0; pom.a= a; pom.b = b; pom.c = c; pom.k = 0; bool warto; q.push(pom); while (!q.empty()) { warto = false; pom = q.front(); q.pop(); if (butla[pom.a] == -1 || butla[pom.a] >= pom.k) { butla[pom.a] = pom.k; } if (butla[pom.b] == -1 || butla[pom.b] >= pom.k) { butla[pom.b] = pom.k; } if (butla[pom.c] == -1 || butla[pom.c] >= pom.k) { //cout << pom.c << "\n"; butla[pom.c] = pom.k; } if (uzyte[{ {pom.a, pom.b}, pom.c}]) continue; uzyte[{ {pom.a, pom.b}, pom.c}] = true; //rozlewanie a,b,c if (pom.a != 0) { // do b if (B > pom.b) { ile_nalac = min(B - pom.b, pom.a); nalewane.a = pom.a - ile_nalac; nalewane.b = pom.b + ile_nalac; nalewane.c = pom.c; nalewane.k = pom.k + 1; q.push(nalewane); } if (C > pom.c) { ile_nalac = min(C - pom.c, pom.a); nalewane.a = pom.a - ile_nalac; nalewane.b = pom.b; nalewane.c = pom.c + ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } if (pom.b != 0) { if (A > pom.a) { ile_nalac = min(A - pom.a, pom.b); nalewane.a = pom.a + ile_nalac; nalewane.b = pom.b - ile_nalac; nalewane.c = pom.c; nalewane.k = pom.k + 1; q.push(nalewane); } if (C > pom.c) { ile_nalac = min(C - pom.c, pom.b); nalewane.a = pom.a; nalewane.b = pom.b - ile_nalac; nalewane.c = pom.c + ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } if (pom.c != 0) { if (A > pom.a) { ile_nalac = min(A - pom.a, pom.c); nalewane.a = pom.a + ile_nalac; nalewane.b = pom.b; nalewane.c = pom.c - ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } if (B > pom.b) { ile_nalac = min(B - pom.b, pom.c); //cout << pom.c << " " << ile_nalac << "\n"; nalewane.a = pom.a; nalewane.b = pom.b + ile_nalac; nalewane.c = pom.c - ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } } for (int i = 0; i <= C; i++) { cout << butla[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 149 150 151 152 153 154 155 156 | #include <iostream> #include <queue> #include <map> #include <utility> using namespace std; int A, B, C; struct my_s { int a, b, c, k; }; const int rozmiar = 1e5 + 5; queue <my_s> q; int butla[rozmiar]; map<pair<pair<int, int>, int>,bool> uzyte; my_s pom; my_s nalewane; int ile_nalac; int main() { for (int i = 0; i < rozmiar; i++) butla[i] = -1; ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; //butla[a] = 0; //butla[b] = 0; //butla[c] = 0; pom.a= a; pom.b = b; pom.c = c; pom.k = 0; bool warto; q.push(pom); while (!q.empty()) { warto = false; pom = q.front(); q.pop(); if (butla[pom.a] == -1 || butla[pom.a] >= pom.k) { butla[pom.a] = pom.k; } if (butla[pom.b] == -1 || butla[pom.b] >= pom.k) { butla[pom.b] = pom.k; } if (butla[pom.c] == -1 || butla[pom.c] >= pom.k) { //cout << pom.c << "\n"; butla[pom.c] = pom.k; } if (uzyte[{ {pom.a, pom.b}, pom.c}]) continue; uzyte[{ {pom.a, pom.b}, pom.c}] = true; //rozlewanie a,b,c if (pom.a != 0) { // do b if (B > pom.b) { ile_nalac = min(B - pom.b, pom.a); nalewane.a = pom.a - ile_nalac; nalewane.b = pom.b + ile_nalac; nalewane.c = pom.c; nalewane.k = pom.k + 1; q.push(nalewane); } if (C > pom.c) { ile_nalac = min(C - pom.c, pom.a); nalewane.a = pom.a - ile_nalac; nalewane.b = pom.b; nalewane.c = pom.c + ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } if (pom.b != 0) { if (A > pom.a) { ile_nalac = min(A - pom.a, pom.b); nalewane.a = pom.a + ile_nalac; nalewane.b = pom.b - ile_nalac; nalewane.c = pom.c; nalewane.k = pom.k + 1; q.push(nalewane); } if (C > pom.c) { ile_nalac = min(C - pom.c, pom.b); nalewane.a = pom.a; nalewane.b = pom.b - ile_nalac; nalewane.c = pom.c + ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } if (pom.c != 0) { if (A > pom.a) { ile_nalac = min(A - pom.a, pom.c); nalewane.a = pom.a + ile_nalac; nalewane.b = pom.b; nalewane.c = pom.c - ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } if (B > pom.b) { ile_nalac = min(B - pom.b, pom.c); //cout << pom.c << " " << ile_nalac << "\n"; nalewane.a = pom.a; nalewane.b = pom.b + ile_nalac; nalewane.c = pom.c - ile_nalac; nalewane.k = pom.k + 1; q.push(nalewane); } } } for (int i = 0; i <= C; i++) { cout << butla[i] << " "; } return 0; } |