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();
	}
}
翰林国际教育资讯二维码