农民约翰有三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数, 最初,A和B桶都是空的,而C桶是装满牛奶的。有时,农民把牛奶从一个桶倒到 另一个桶中,直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约, 牛奶不会有丢失。
描述
写一个程序去帮助农民找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性。
格式
PROGRAM NAME: milk3
INPUT FORMAT:
(file milk3.in)
单独的一行包括三个整数A,B和C。
OUTPUT FORMAT:
(file milk3.out)
只有一行,升序地列出当A桶是空的时候,C桶牛奶所剩量的所有可能性。
SAMPLE INPUT 1
8 9 10
SAMPLE OUTPUT 1
1 2 8 9 10
SAMPLE INPUT 2
2 5 10
SAMPLE OUTPUT 2
5 6 7 8 9 10
分析
Way :DFS 因为牛奶的总量是不变的,所以可以用a,b中的牛奶量做状态,初始状态是(0,0),每次只能有6种选择,a倒b,a倒c,b倒a,b倒c,c倒a,c倒b。用一个数组vis[i][j]判重,s[i]记录c中所有可能值(s[i]=true表示c中可能出现i),如果当前状态是(0,x),那么s[mc -x]=true,最后输出s中所有true的就可以了。
CODE:
/* ID: 138_3531 LANG: C++ TASK: milk3 */ #include <iostream> #include <fstream> using namespace std; ifstream fin("milk3.in"); ofstream fout("milk3.out"); int a, b, c, tf[21][21] = {0}; void dfs(int i, int k) { if (tf[i][k])return; tf[i][k] = 1; dfs(0, k); dfs(i, 0); if (i >= b - k)dfs(i - b + k, b); else dfs(0, i + k); if (k >= a - i)dfs(a, k - a + i); else dfs(i + k, 0); int j = c - i - k; if (j >= a - i)dfs(a, k); else dfs(i + j, k); if (j >= b - k)dfs(i, b); else dfs(i, k + j); } int main() { fin >> a >> b >> c; dfs(0, 0); for (int i = 20, ge = 0; i >= 0; i--) if (tf[0][i]) { if (ge)fout << ' '; else ge = 1; fout << c - i; } fout << endl; }