#include <bits/stdc++.h> using namespace std; struct pos{ int a,b,c; bool operator < (const pos &abc){ return tie(a,b,c) < tie(abc.a,abc.b,abc.c); } }; bool operator < (const pos &abc, const pos &xyz){ return tie(xyz.a,xyz.b,xyz.c) < tie(abc.a,abc.b,abc.c); } const int N = 300005; const int INF = 999999999; int dist[N]; map<pos,bool> vis; int sizA,sizB,sizC; void bfs(pos s){ queue<pair<int,pos>> q; // (distance_to_position, position) int curDist = 0; q.push({0,s}); dist[s.a] = 0; // a dist[s.b] = 0; // b dist[s.c] = 0; // c vis[s] = 1; while(!q.empty()){ s = q.front().second; curDist = q.front().first; q.pop(); // Z A do B cale if(!vis[{0, min(s.a+s.b,sizB), s.c}]){ vis[{0, min(s.a+s.b,sizB), s.c}] = 1; dist[0] = min(dist[0], curDist+1); dist[min(s.a+s.b,sizB)] = min(dist[min(s.a+s.b,sizB)], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{0, min(s.a+s.b,sizB), s.c}}); } // Z A do B do zapelnienia if(s.a>(sizB-s.b) && !vis[{s.a-(sizB-s.b), sizB, s.c}]){ vis[{s.a-(sizB-s.b), sizB, s.c}] = 1; dist[s.a-(sizB-s.b)] = min(dist[s.a-(sizB-s.b)], curDist+1); dist[sizB] = min(dist[sizB], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{s.a-(sizB-s.b), sizB, s.c}}); } // Z A do C cale if(!vis[{0, s.b, min(s.a+s.c,sizC)}]){ vis[{0, s.b, min(s.a+s.c,sizC)}] = 1; dist[0] = min(dist[0], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[min(s.a+s.c,sizC)] = min(dist[min(s.a+s.c,sizC)], curDist+1); q.push({curDist+1,{0, s.b, min(s.a+s.c,sizC)}}); } // Z A do C do zapelnienia if(s.a>(sizC-s.c) && !vis[{s.a-(sizC-s.c), s.b, sizC}]){ vis[{s.a-(sizC-s.c), s.b, sizC}] = 1; dist[s.a-(sizC-s.c)] = min(dist[s.a-(sizC-s.c)], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[sizC] = min(dist[sizC], curDist+1); q.push({curDist+1,{s.a-(sizC-s.c), s.b, sizC}}); } // Z B do A cale if(!vis[{min(s.a+s.b,sizA), 0, s.c}]){ vis[{min(s.a+s.b,sizA), 0, s.c}] = 1; dist[min(s.a+s.b,sizA)] = min(dist[min(s.a+s.b,sizA)], curDist+1); dist[0] = min(dist[0], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{min(s.a+s.b,sizA), 0, s.c}}); } // Z B do A do zapelnienia if(s.b>(sizA-s.a) && !vis[{sizA, s.b-(sizA-s.a), s.c}]){ vis[{sizA, s.b-(sizA-s.a), s.c}] = 1; dist[sizA] = min(dist[sizA], curDist+1); dist[s.b-(sizA-s.a)] = min(dist[s.b-(sizA-s.a)], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{sizA, s.b-(sizA-s.a), s.c}}); } // Z B do C cale if(!vis[{s.a, 0, min(s.b+s.c,sizC)}]){ vis[{s.a, 0, min(s.b+s.c,sizC)}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[0] = min(dist[0], curDist+1); dist[min(s.b+s.c,sizC)] = min(dist[min(s.b+s.c,sizC)], curDist+1); q.push({curDist+1,{s.a, 0, min(s.b+s.c,sizC)}}); } // Z B do C do zapelnienia if(s.b>(sizC-s.c) && !vis[{s.a, s.b-(sizC-s.c), sizC}]){ vis[{s.a, s.b-(sizC-s.c), sizC}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[s.b-(sizC-s.c)] = min(dist[s.b-(sizC-s.c)], curDist+1); dist[sizC] = min(dist[sizC], curDist+1); q.push({curDist+1,{s.a, s.b-(sizC-s.c), sizC}}); } // Z C do A cale if(!vis[{min(s.a+s.c,sizA), s.b, 0}]){ vis[{min(s.a+s.c,sizA), s.b, 0}] = 1; dist[min(s.a+s.c,sizA)] = min(dist[min(s.a+s.c,sizA)], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[0] = min(dist[0], curDist+1); q.push({curDist+1,{min(s.a+s.c,sizA), s.b, 0}}); } // Z C do A do zapelnienia if(s.c>(sizA-s.a) && !vis[{sizA, s.b, s.c-(sizA-s.a)}]){ vis[{sizA, s.b, s.c-(sizA-s.a)}] = 1; dist[sizA] = min(dist[sizA], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[s.c-(sizA-s.a)] = min(dist[s.c-(sizA-s.a)], curDist+1); q.push({curDist+1,{sizA, s.b, s.c-(sizA-s.a)}}); } // Z C do B cale if(!vis[{s.a, min(s.b+s.c,sizB), 0}]){ vis[{s.a, min(s.b+s.c,sizB), 0}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[min(s.b+s.c,sizB)] = min(dist[min(s.b+s.c,sizB)], curDist+1); dist[0] = min(dist[0], curDist+1); q.push({curDist+1,{s.a, min(s.b+s.c,sizB), 0}}); } // Z C do B do zapelnienia if(s.c>(sizB-s.b) && !vis[{s.a, sizB, s.c-(sizB-s.b)}]){ vis[{s.a, sizB, s.c-(sizB-s.b)}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[sizB] = min(dist[sizB], curDist+1); dist[s.c-(sizB-s.b)] = min(dist[s.c-(sizB-s.b)], curDist+1); q.push({curDist+1,{s.a, sizB, s.c-(sizB-s.b)}}); } } return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int a,b,c; for(int i=0; i<N; ++i){ dist[i] = INF; } cin >> sizA >> sizB >> sizC; cin >> a >> b >> c; bfs({a,b,c}); for(int i=0; i<sizC+1; ++i){ if(dist[i] >= INF){ cout << -1; }else{ cout << dist[i]; } cout << " "; } 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 <bits/stdc++.h> using namespace std; struct pos{ int a,b,c; bool operator < (const pos &abc){ return tie(a,b,c) < tie(abc.a,abc.b,abc.c); } }; bool operator < (const pos &abc, const pos &xyz){ return tie(xyz.a,xyz.b,xyz.c) < tie(abc.a,abc.b,abc.c); } const int N = 300005; const int INF = 999999999; int dist[N]; map<pos,bool> vis; int sizA,sizB,sizC; void bfs(pos s){ queue<pair<int,pos>> q; // (distance_to_position, position) int curDist = 0; q.push({0,s}); dist[s.a] = 0; // a dist[s.b] = 0; // b dist[s.c] = 0; // c vis[s] = 1; while(!q.empty()){ s = q.front().second; curDist = q.front().first; q.pop(); // Z A do B cale if(!vis[{0, min(s.a+s.b,sizB), s.c}]){ vis[{0, min(s.a+s.b,sizB), s.c}] = 1; dist[0] = min(dist[0], curDist+1); dist[min(s.a+s.b,sizB)] = min(dist[min(s.a+s.b,sizB)], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{0, min(s.a+s.b,sizB), s.c}}); } // Z A do B do zapelnienia if(s.a>(sizB-s.b) && !vis[{s.a-(sizB-s.b), sizB, s.c}]){ vis[{s.a-(sizB-s.b), sizB, s.c}] = 1; dist[s.a-(sizB-s.b)] = min(dist[s.a-(sizB-s.b)], curDist+1); dist[sizB] = min(dist[sizB], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{s.a-(sizB-s.b), sizB, s.c}}); } // Z A do C cale if(!vis[{0, s.b, min(s.a+s.c,sizC)}]){ vis[{0, s.b, min(s.a+s.c,sizC)}] = 1; dist[0] = min(dist[0], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[min(s.a+s.c,sizC)] = min(dist[min(s.a+s.c,sizC)], curDist+1); q.push({curDist+1,{0, s.b, min(s.a+s.c,sizC)}}); } // Z A do C do zapelnienia if(s.a>(sizC-s.c) && !vis[{s.a-(sizC-s.c), s.b, sizC}]){ vis[{s.a-(sizC-s.c), s.b, sizC}] = 1; dist[s.a-(sizC-s.c)] = min(dist[s.a-(sizC-s.c)], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[sizC] = min(dist[sizC], curDist+1); q.push({curDist+1,{s.a-(sizC-s.c), s.b, sizC}}); } // Z B do A cale if(!vis[{min(s.a+s.b,sizA), 0, s.c}]){ vis[{min(s.a+s.b,sizA), 0, s.c}] = 1; dist[min(s.a+s.b,sizA)] = min(dist[min(s.a+s.b,sizA)], curDist+1); dist[0] = min(dist[0], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{min(s.a+s.b,sizA), 0, s.c}}); } // Z B do A do zapelnienia if(s.b>(sizA-s.a) && !vis[{sizA, s.b-(sizA-s.a), s.c}]){ vis[{sizA, s.b-(sizA-s.a), s.c}] = 1; dist[sizA] = min(dist[sizA], curDist+1); dist[s.b-(sizA-s.a)] = min(dist[s.b-(sizA-s.a)], curDist+1); dist[s.c] = min(dist[s.c], curDist+1); q.push({curDist+1,{sizA, s.b-(sizA-s.a), s.c}}); } // Z B do C cale if(!vis[{s.a, 0, min(s.b+s.c,sizC)}]){ vis[{s.a, 0, min(s.b+s.c,sizC)}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[0] = min(dist[0], curDist+1); dist[min(s.b+s.c,sizC)] = min(dist[min(s.b+s.c,sizC)], curDist+1); q.push({curDist+1,{s.a, 0, min(s.b+s.c,sizC)}}); } // Z B do C do zapelnienia if(s.b>(sizC-s.c) && !vis[{s.a, s.b-(sizC-s.c), sizC}]){ vis[{s.a, s.b-(sizC-s.c), sizC}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[s.b-(sizC-s.c)] = min(dist[s.b-(sizC-s.c)], curDist+1); dist[sizC] = min(dist[sizC], curDist+1); q.push({curDist+1,{s.a, s.b-(sizC-s.c), sizC}}); } // Z C do A cale if(!vis[{min(s.a+s.c,sizA), s.b, 0}]){ vis[{min(s.a+s.c,sizA), s.b, 0}] = 1; dist[min(s.a+s.c,sizA)] = min(dist[min(s.a+s.c,sizA)], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[0] = min(dist[0], curDist+1); q.push({curDist+1,{min(s.a+s.c,sizA), s.b, 0}}); } // Z C do A do zapelnienia if(s.c>(sizA-s.a) && !vis[{sizA, s.b, s.c-(sizA-s.a)}]){ vis[{sizA, s.b, s.c-(sizA-s.a)}] = 1; dist[sizA] = min(dist[sizA], curDist+1); dist[s.b] = min(dist[s.b], curDist+1); dist[s.c-(sizA-s.a)] = min(dist[s.c-(sizA-s.a)], curDist+1); q.push({curDist+1,{sizA, s.b, s.c-(sizA-s.a)}}); } // Z C do B cale if(!vis[{s.a, min(s.b+s.c,sizB), 0}]){ vis[{s.a, min(s.b+s.c,sizB), 0}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[min(s.b+s.c,sizB)] = min(dist[min(s.b+s.c,sizB)], curDist+1); dist[0] = min(dist[0], curDist+1); q.push({curDist+1,{s.a, min(s.b+s.c,sizB), 0}}); } // Z C do B do zapelnienia if(s.c>(sizB-s.b) && !vis[{s.a, sizB, s.c-(sizB-s.b)}]){ vis[{s.a, sizB, s.c-(sizB-s.b)}] = 1; dist[s.a] = min(dist[s.a], curDist+1); dist[sizB] = min(dist[sizB], curDist+1); dist[s.c-(sizB-s.b)] = min(dist[s.c-(sizB-s.b)], curDist+1); q.push({curDist+1,{s.a, sizB, s.c-(sizB-s.b)}}); } } return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int a,b,c; for(int i=0; i<N; ++i){ dist[i] = INF; } cin >> sizA >> sizB >> sizC; cin >> a >> b >> c; bfs({a,b,c}); for(int i=0; i<sizC+1; ++i){ if(dist[i] >= INF){ cout << -1; }else{ cout << dist[i]; } cout << " "; } return 0; } |