FindMin.java

import java.util.*;
import java.io.*;

//2013 Facebook Hacker Cup Qualification Round
//Problem 3: Find the Min http://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420

public class FindMin {
    static Scanner in;

	public static void main(String[] args) throws Exception {
		in = new Scanner(new File("FindMin.in"));
		new FindMin().run();
	}

	void run() {
		int t = in.nextInt(), counter = 0;

		for (int i = 0; i < t; i++) {
			int n = in.nextInt(), k = in.nextInt(), a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), r = in.nextInt();
			System.out.printf("Case #%d: %d%n", ++counter, solve(n, k, a, b, c, r));
		}
	}

	long solve(int n, int k, int a, int b, int c, int r) {
		long[] m = generate(k, a, b, c, r);
		int cons = 2 * k + 1;
		int[] t = new int[cons];

		for (int i=0; i<k; i++) {
			if (m[i] < cons) 
				t[(int) m[i]]++;
		}

		for (int i=k; i<m.length; i++) {
			int min = 0;

			while (t[min++] > 0);
			m[i] = min - 1;

			if (m[i-k] < cons)
				t[(int) m[i-k]]--;

			t[min-1]++;
		}

		return m[k + ((n-1-k) % (k+1))];
	}

	long[] generate(int k, int a, int b, int c, int r) {
		long[] m = new long[2 * k + 1];
		m[0] = a;

		for (int i=1; i<k; i++)
			m[i] = (b * m[i-1] + c) % r;

		return m;
	}
}