Mother's Milk - USACO 1.4.4

mother'smilk - codetrick

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10  

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10  

SAMPLE INPUT (file milk3.in)

2 5 10  

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

http://mangogao.com/read/89.html
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到 另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约， 牛奶不会有丢失。
写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

http://jusaco.blogspot.com/2013/07/mothers-milk-training.html
X. DFS
http://www.icycandy.com/blog/usaco-1-4-4-mothers-milk
https://tausiq.wordpress.com/2010/11/26/usaco-mothers-milk/

设res[j]为C桶中牛奶量为j的可能性

status[i][j]为A桶有i牛奶,C桶有j牛奶的可能性,初态为i==0;j==C;

当i==0时置res[j]=true;

总共有六种倒法A->B,A->C,B->A,B->C,C->A,C->B

对每种status,分别搜索这六种倒法.

http://leonlu.iteye.com/blog/1125500

用DFS解。用searched[x][y]数组记录搜索过的状态，不使用三维数组是因为前2维决定了第三维。用amount[z]的布尔值记录当x=0时z的值。 

	private static boolean[][] searched = new boolean[21][21];
	private static boolean[] amount = new boolean[21];
	private static int a,b,c;
	public static void main(String[] args) throws Exception{
	BufferedReader in = new BufferedReader(new FileReader("milk3.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("milk3.out")),true);
	//read data
	StringTokenizer st = new StringTokenizer(in.readLine());
	a = Integer.parseInt(st.nextToken());
	b = Integer.parseInt(st.nextToken());
	c = Integer.parseInt(st.nextToken());
	dfs(0,0,c);
	for (int i = 0;i < c;i++)
	if (amount[i])
	out.print(i + " ");
	out.println(c);
	System.exit(0);
	}
	private static void dfs(int x, int y, int z){
	if(searched[x][y]) return;
	searched[x][y] = true;
	if(x == 0) amount[z] = true;
	if (x>0 && y<b)
	dfs(max(0,x+y-b),min(b,x+y),z);
	if (x>0 && z<c)
	dfs(max(0,x+z-c),y,min(c,x+z));
	if (y>0 && x<a)
	dfs(min(a,y+x),max(0,y+x-a),z);
	if (y>0 && z<c)
	dfs(x,max(0,y+z-c), min(c,y+z));
	if (z>0 && x<a)
	dfs(min(a,z+x),y,max(0,z+x-a));
	if (z>0 && y<b)
	dfs(x,min(b,z+y),max(0,z+y-b));
	}

bool res[21]={0};
bool status[21][21]={0}; //status[i][j]表示A有i牛奶，C有j牛奶的可能
int a,b,c,p,q;
 
int main()
{
    ifstream fin("milk3.in");
    ofstream fout("milk3.out");
 
    int s=0,i,j=0;
    fin>>a>>b>>c;
    search(0,c);
 
    for (i=0;i<=20;i++) if (res[i]) s++;
    for (i=0;i<=20;i++)
    {
        if (res[i])
        {
            fout<<i;
            j++;
            if (j==s) fout<<endl;
            else fout<<’ ‘;
        }
    }
 
    fin.close();
 
    fout.close();
 
    return 0;
}
 
void search(int ma,int mc)
{
    if (status[ma][mc]) return;
 
    int mb=c-ma-mc;
    status[ma][mc]=true;
    if (ma==0) res[mc]=true;
 
    search(ma-min(ma,b-mb),mc); //a->b
    search(ma-min(ma,c-mc),mc+min(ma,c-mc)); //a->c
    search(ma+min(mb,a-ma),mc); //b->a
    search(ma,mc+min(mb,c-mc)); //b->c
    search(ma+min(a-ma,mc),mc-min(a-ma,mc)); //c->a ma + min(mc,a-ma),
    search(ma,mc-min(b-mb,mc)); //c->b
}

X. BFS
http://qingtangpaomian.iteye.com/blog/1635111

用BFS逐层产生可能有的A,B,C三个桶的牛奶数量。如果已经产生过了则不用进入bfs的队列了，所以我们用一个hash表记录所有已经产生的状态。

          如果bfs的队列当中没有元素了，则程序结束，输出所有已经产生的结果。

1.     public static void main(String[] args) {  
2.         try {  
3.             Scanner in = new Scanner(new BufferedReader(new FileReader("milk3.in")));  
4.             PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("milk3.out")));  
5.               
6.             LinkedList<status> list = new LinkedList<status>();//bfs队列  
7.             HashSet<status> hash = new HashSet<status>();//记录已经产生过的a,b,c三个桶的容量状态  
8.             HashSet<Integer> result = new HashSet<Integer>();//记录已经产生的c桶的状态  
9.               
10.             int a = in.nextInt();  
11.             int b = in.nextInt();  
12.             int c = in.nextInt();  
13.             status init = new status(0,0,c);  
14.             list.add(init);  
15.               
16.             while (list.size()!=0){//编列bfs队列  
17.                 status temp = list.remove(0);  
18.                 if (hash.contains(temp)){  
19.                     //doNothing  
20.                 } else {  
21.                     hash.add(temp);  
22.                     //如果a桶的容量为空，则在结果集当中加入c的状态  
23.                     if (temp.a==0){  
24.                         result.add(temp.c);  
25.                     }  
26.                     //遍历所有可能的倒牛奶方式  
27.                     //a->b  
28.                     if (temp.a >= b-temp.b){  
29.                         status node = new status(temp.a-b+temp.b,b,temp.c);  
30.                         if (!hash.contains(node)){  
31.                             list.add(node);  
32.                         }  
33.                     }else{  
34.                         status node = new status(0,temp.b+temp.a,temp.c);  
35.                         if (!hash.contains(node)){  
36.                             list.add(node);  
37.                         }  
38.                     }  
39.                     //a->c  
40.                     if (temp.a >= c-temp.c){  
41.                         status node = new status(temp.a-c+temp.c,temp.b,c);  
42.                         if (!hash.contains(node)){  
43.                             list.add(node);  
44.                         }  
45.                     }else{  
46.                         status node = new status(0,temp.b,temp.c+temp.a);  
47.                         if (!hash.contains(node)){  
48.                             list.add(node);  
49.                         }  
50.                     }  
51.                     //b->a  
52.                     if (temp.b >= a-temp.a){  
53.                         status node = new status(a,temp.b-a+temp.a,temp.c);  
54.                         if (!hash.contains(node)){  
55.                             list.add(node);  
56.                         }  
57.                     }else{  
58.                         status node = new status(temp.a+temp.b,0,temp.c);  
59.                         if (!hash.contains(node)){  
60.                             list.add(node);  
61.                         }  
62.                     }  
63.                     //b->c  
64.                     if (temp.b >= c-temp.c){  
65.                         status node = new status(temp.a,temp.b-c+temp.c,c);  
66.                         if (!hash.contains(node)){  
67.                             list.add(node);  
68.                         }  
69.                     }else {  
70.                         status node = new status(temp.a,0,temp.c+temp.b);  
71.                         if (!hash.contains(node)){  
72.                             list.add(node);  
73.                         }  
74.                     }  
75.                       
76.                     //c->a  
77.                     if (temp.c >= a-temp.a){  
78.                         status node = new status(a,temp.b,temp.c-a+temp.a);  
79.                         if (!hash.contains(node)){  
80.                             list.add(node);  
81.                         }  
82.                     }else{  
83.                         status node = new status(temp.a+temp.c,temp.b,0);  
84.                         if (!hash.contains(node)){  
85.                             list.add(node);  
86.                         }  
87.                     }  
88.                       
89.                     //c->b  
90.                     if (temp.c >= b-temp.b){  
91.                         status node = new status(temp.a,b,temp.c-b+temp.b);  
92.                         if (!hash.contains(node)){  
93.                             list.add(node);  
94.                         }  
95.                     }else {  
96.                         status node = new status(temp.a,temp.b+temp.c,0);  
97.                         if (!hash.contains(node)){  
98.                             list.add(node);  
99.                         }  
100.                     }  
101.                       
102.                 }  
103.             }  
104.             Integer[] out = new Integer[result.size()];  
105.             result.toArray(out);  
106.             Arrays.sort(out);  
107.             StringBuilder sb = new StringBuilder();  
108.             for (int i = 0;i<out.length;i++){  
109.                 sb.append(out[i]+" ");  
110.             }  
111.             sb.deleteCharAt(sb.length()-1);  
112.             pw.println(sb);  
113.             pw.close();  
114.             in.close();  
115.         } catch (Exception e) {  
116.             // TODO Auto-generated catch block  
117.             e.printStackTrace();  
118.         }  
119.     }  
120. }  
121.   
122. class status {  
123.     int a ;  
124.     int b ;  
125.     int c ;  
126.       
127.     public status(int a ,int b ,int c){  
128.         this.a = a;  
129.         this.b = b;  
130.         this.c = c;  
131.     }  
132.       
133.     @Override  
134.     public boolean equals(Object obj) {  
135.         status sta = (status)obj;  
136.         if (this.a == sta.a && this.b == sta.b && this.c == sta.c){  
137.             return true;  
138.         } else {  
139.             return false;  
140.         }  
141.     }  
142.       
143.     @Override  
144.     public int hashCode() {  
145.         // TODO Auto-generated method stub  
146.         return a*1 + b*2 + c*3;  
147.     }  
148. }

http://jackneus.com/programming-archives/mothers-milk/

Read full article from mother'smilk - codetrick