P1215 [USACO1.4] 母亲的牛奶 Mother’s Milk

题目描述

农民约翰有三个容量分别是 $a,b,c$ 升的桶。

最初，$a,b$ 桶都是空的，而 $c$ 桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。

当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当 $a$ 桶是空的时候，$c$ 桶中牛奶所剩量的所有可能性。

输入格式

单独的一行包括三个整数 $a,b,c$。

输出格式

只有一行，升序地列出当 $a$ 桶是空的时候，$c$ 桶牛奶所剩量的所有可能性。

输入输出样例 #1

输入 #1

8 9 10

输出 #1

1 2 8 9 10

输入输出样例 #2

输入 #2

2 5 10

输出 #2

5 6 7 8 9 10

说明/提示

【数据范围】
对于 $100\%$ 的数据，$1\le a,b,c\le 20$。

题目翻译来自NOCOW。

USACO Training Section 1.4

C++实现

#include
#include
#include
const int MAX = 22;
bool milk[MAX] = {0};
bool vis[MAX][MAX][MAX] = {0};
static int bkt[3];
void dfs(int a[]) {
if (vis[a[0]][a[1]][a[2]]) return;
vis[a[0]][a[1]][a[2]] = true;
if (a[0] == 0) milk[a[2]] = true;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (j == i) continue;
if (a[j] < bkt[j] && a[i] > 0) {
int rec = std::min(bkt[j] - a[j], a[i]);
int b[3];
memcpy(b, a, sizeof(int)*3);
b[i] -= rec, b[j] += rec;
dfs(b);
}
}
}
}
int main() {
int &A = bkt[0], &B = bkt[1], &C = bkt[2];
scanf(" %d %d %d", &A, &B, &C);
int a[3] = {0,0,C};
dfs(a);
for (int i = 0; i < C; ++i) {
if (milk[i]) printf(“%d “, i);
}
printf(”%d\n”, C);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容