Last active
December 11, 2015 21:18
-
-
Save Bekt/4661690 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment