机场建设管理投资有限责任公司网站,承德建设企业网站,重庆cms建站模板,中小企业网站制作平台农夫约翰有三个容量分别为 A , B , C A,B,C A,B,C 升的挤奶桶。
最开始桶 A A A 和桶 B B B 都是空的#xff0c;而桶 C C C 里装满了牛奶。
有时#xff0c;约翰会将牛奶从一个桶倒到另一个桶中#xff0c;直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过…农夫约翰有三个容量分别为 A , B , C A,B,C A,B,C 升的挤奶桶。
最开始桶 A A A 和桶 B B B 都是空的而桶 C C C 里装满了牛奶。
有时约翰会将牛奶从一个桶倒到另一个桶中直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿并且不会有任何牛奶的浪费。
请你编写一个程序判断当 A A A 桶是空的时候 C C C 桶中可能包含多少升牛奶找出所有的可能情况。
输入格式
共一行包含三个整数 A , B , C A,B,C A,B,C。
输出格式
共一行包含若干个整数表示 C C C 桶中牛奶存量的所有可能情况请将这些数字按升序排列。
数据范围 1 ≤ A , B , C ≤ 20 1≤A,B,C≤20 1≤A,B,C≤20
输入样例1
8 9 10输出样例1
1 2 8 9 10输入样例2
2 5 10输出样例2
5 6 7 8 9 10思路
以输入样例1模拟 可以发现每个桶都可以倒入另外两个桶中 也就是说在桶的数量为 3 3 3 的情况下共有 3 × 2 6 3 \times 2 6 3×26 种可能。
因此可以枚举 6 种状态或者循环遍历所有所有状态。
这里我们可以用数组模拟队列每当有新的状态时就把新状态入队通过遍历队列进行宽搜。
代码
#includeiostream
#includealgorithm
using namespace std;const int N 21;
int A, B, C; //桶的容量
struct node {int a, b, c;
} q[N * N * N];
bool st[N][N][N];//标记状态int bfs() {int hh 0, tt 0; //队头队尾q[0] {0, 0, C};st[0][0][C] true;int W[3] {A, B, C}; //桶的容量while (hh tt) {auto t q[hh];for (int i 0; i 3; i) //将i桶倒入j桶for (int j 0; j 3; j)if (i ! j) {int w[3] {t.a, t.b, t.c};int r min(w[i], W[j] - w[j]);w[i] - r, w[j] r;int a w[0], b w[1], c w[2];if (!st[a][b][c]) {st[a][b][c] true; //标记q[tt] {a, b, c}; }}}}int main() {cin A B C;bfs();for (int i 0; i C; i)for (int j 0; j B; j)if (st[0][j][i]) {cout i ;break;}return 0;
}
