USACO 2016 February Contest, Silver Problem 3. Milk Pails

原題下載

USACO2016-FEB-S3

答案

(Analysis by Nick Wu)

In this problem, we have two buckets and we can either fill them, empty them, or pour one into the other until we fill a bucket or empty one. We want to compute how close we can get to having M units of milk after K of these operations.

It's hard to answer the question: Can we end up with exactly M units of milk in these two buckets after at most K operations? It's easier to answer the question: Can we end up with A units of milk in the size X bucket and B units of milk in the size Y bucket after at most K operations?

Imagine that we have A units of milk in the size X bucket and B units of milk in the size Y bucket after at most L operations. With this information, there are several possible states that are attainable after at most L+1 operations. For example, just by emptying or filling buckets, we can get the following four states:

• X units of milk in the size X bucket and B units of milk in the size Y bucket.
• 0 units of milk in the size X bucket and B units of milk in the size Y bucket.
• A units of milk in the size X bucket and Y units of milk in the size Y bucket.
• A units of milk in the size X bucket and 0 units of milk in the size Y bucket.

We can also pour milk from one of the buckets to the other.

We maintain all attainable states as we increase the number of operations we attempt.

Here is my Java code.

import java.io.*;
import java.util.*;
public class pails {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("pails.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("pails.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		boolean[][] can = new boolean[x+1][y+1];
		can[0][0] = true;
		for(int operationNum = 0; operationNum < k; operationNum++) {
			// if can[A][B] is true, then after at most operationNum operations,
			// it is possible to end with A units of milk in the size X bucket
			// and B units of milk in the size Y bucket.
			boolean[][] next = new boolean[x+1][y+1];
			for(int i = 0; i < can.length; i++) {
				for(int j = 0; j < can[i].length; j++) {
					if(!can[i][j]) continue;
					// we can always maintain the same state
					next[i][j] = true;
					// empty size X bucket
					next[0][j] = true;
					// fill size X bucket
					next[x][j] = true;
					// empty size Y bucket
					next[i][0] = true;
					// fill size Y bucket
					next[i][y] = true;
					// pour from size X bucket to size Y bucket
					int moveRight = Math.min(i, y - j);
					next[i-moveRight][j+moveRight] = true;
					// pour from size Y bucket to size X bucket
					int moveLeft = Math.min(x - i, j);
					next[i+moveLeft][j-moveLeft] = true;
				}
			}
			can = next;
		}
		int ret = Integer.MAX_VALUE;
		for(int i = 0; i < can.length; i++) {
			for(int j = 0; j < can[i].length; j++) {
				if(!can[i][j]) continue;
				ret = Math.min(ret, Math.abs(i+j-m));
			}
		}
		pw.println(ret);
		pw.close();
	}
}

以上就是關于【USACO 2016 February Contest, Silver Problem 3. Milk Pails】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！