GCJ2010 Qualification Round C "Theme Park"

問題：http://code.google.com/codejam/contest/dashboard?c=433101#s=p2

import java.io.File;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class ThemePark {
	public static void main(String[] args) throws Exception {
		String filename = "C-large";
		Scanner scan = new Scanner(new File(filename + ".in"));
		PrintWriter out = new PrintWriter(new File(filename + ".out"));

		for (int T = scan.nextInt(), t = 0; t++ < T;) {
			int R = scan.nextInt();
			int k = scan.nextInt();
			int N = scan.nextInt();
			List<Integer> g = new ArrayList<Integer>();
			for (int i = 0; i < N; i++) {
				g.add(scan.nextInt());
			}
			List<Integer> l = new ArrayList<Integer>();
			int n = 0;
			List<Integer> list = new ArrayList<Integer>();
			list.add(n);
			for (int i = 0; i < 2 * N; i++) {
				int h = 0, c = 0;
				for (c = 0; c < g.size() && h + g.get(0) <= k; c++) {
					h += g.get(0);
					Collections.rotate(g, -1);
				}
				n = (n + c) % g.size();
				list.add(n);
				l.add(h);
				if (list.indexOf(n) != list.lastIndexOf(n)) {
					break;
				}
			}
			int loopStart = list.indexOf(list.get(list.size() - 1));
			List<Integer> untilLoop = l.subList(0, loopStart);
			List<Integer> loopList = l.subList(loopStart, l.size());
			int loopCount = (R - untilLoop.size()) / loopList.size();
			int loopExt = (R - untilLoop.size()) % loopList.size();
			List<Integer> extLoop = l.subList(loopStart, loopStart + loopExt);
			BigDecimal count = BigDecimal.valueOf(0);
			for (int c : loopList) {
				count = count.add(BigDecimal.valueOf(c));
			}
			count = count.multiply(BigDecimal.valueOf(loopCount));
			for (int c : untilLoop) {
				count = count.add(BigDecimal.valueOf(c));
			}
			for (int c : extLoop) {
				count = count.add(BigDecimal.valueOf(c));
			}
			out.printf("Case #%d: %s\n", t, count);
		}
		out.flush();
	}
}