USACO 2016 February Contest, Bronze Problem 2. Circular Barn

原題下載

USACO2016-FEB-B2

答案

(Analysis by Nick Wu)

For this problem, we can try unlocking all possible starting doors and seeing how far each cow travels.

One tricky implementation detail here is that the barn is circular, so if we store the data in an array and we assume that the index to inspect is simply the sum of the unlocked door index and the distance to travel, we might exceed the bounds of the array. Because the barn is circular, the barn that would be at location N is actually the barn at location 0, so we can just take the remainder of the sum modulo N.

Here is my Java code.

import java.io.*;
import java.util.*;
public class cbarn {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("cbarn.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cbarn.out")));
		// read in N
		int n = Integer.parseInt(br.readLine());
		int[] cows = new int[n];
		// read in how many cows need to be in each room
		for(int i = 0; i < n; i++) {
			cows[i] = Integer.parseInt(br.readLine());
		}
		// the answer cannot exceed N * N * 100, since there are at most 100N cows, each of which can move at most N
		int ans = n * n * 100;
		for(int unlock = 0; unlock < n; unlock++) {
			// assume we unlock the door at index "unlock", compute the distance all cows travel
			int currentDistance = 0;
			for(int offset = 0; offset < n; offset++) {
				// count how many cows have to walk a distance of "offset"
				currentDistance += offset * cows[(unlock+offset)%n];
			}
			// update the answer
			if(currentDistance < ans) {
				ans = currentDistance;
			}
		}
		// print the answer
		pw.println(ans);
		// close output stream
		pw.close();
	}
}

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

往期文章閱讀推薦：

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

耗時一年備考 USACO 卻毫無收獲？一文教你找準最佳備考起步時間！