BearEats
2015 TCO Parallel 3B · 2015-04-08 · by Errichto
Problem Statement
Bear Limak and deer Evil have N cookies with various flavors. Cookies are numbered 0 through N-1. Bears and deer are natural enemies so Limak and Evil don't want to eat together. They decided to divide cookies by playing a simple game. They will alternately take one cookie. Limak starts. The game ends when there are no more cookies.
As you can guess, bears and deer prefer different flavors. The i-th cookie has value A[i] for Limak and value B[i] for Evil. We define Limak's score as sum of A[i] of his cookies and Evil's score as sum of B[i] of his cookies.
Limak knows his opponent's strategy. Evil always takes a cookie with the biggest B[i]. In case of tie he takes a cookie with the biggest A[i] (from cookies with the biggest B[i]).
Limak wants to maximize the difference between his and Evil's score. Help him and find the maximum possible value of L-E, where L denotes Limak's score and E denotes Evil's score.
The description of cookies is provided in the form of a pseudorandom generator.
You are given the
for i between 0 and N-1, inclusive:
R = (C * R + D) modulo (10^9+7);
A[i] = R % A_MAX;
R = (C * R + D) modulo (10^9+7);
B[i] = R % B_MAX;
Note that A[i] will be between 0 and A_MAX-1, inclusive. And B[i] will be between 0 and B_MAX-1, inclusive.
Notes
- N will be between 1 and 200,000, inclusive.
- R, C and D will be between 0 and 1,000,000,000, inclusive.
- A_MAX and B_MAX will be between 1 and 1,000,000,000, inclusive.
Constraints
3 4 4 1 11 15 Returns: -3
A = {6,2,4}, B = {9,14,4}. Limak should take the second cookie - (2,14). It has value A[i]=2 for him. Evil wants a cookie with the bigest B[i] so he takes (6,9). Limak can take the last cookie (4,4) and his score is 2+4=6. Evil's score is 9 so difference is 6-9 = -3. Limak can't achieve a better difference.
5 2 3 0 14 40 Returns: 4
A = {6, 12, 10, 6, 12}, B = {18, 2, 18, 2, 18}. Optimal start for Limak is to take the cookie (12,18). There are two cookies with the biggest B[i] now and Evil takes the one with bigger A[i] - (10, 18). Limak takes (6,18), Evil (12,2) and Limak (6,2). Limak has score 12+6+6 = 24. Evil has score 18+2 = 20.
4 938593858 538591850 384025833 885912358 3405 Returns: 1452754016
A = {224250140, 715072124, 737687500, 357608742}, B = {2859, 908, 1144, 2749}. Evil wants first cookie and the last one and Limak should allow him to do it. Limak ends with score 737687500 + 715072124 and Evil with 2859 + 2749.
200000 999998741 999997411 64592149 57 75 Returns: 462494
1 1 1 1 1 1 Returns: 0
empty test, it can be changed into example
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearEats with a public method long long getDifference(int N, int R, int C, int D, int A_MAX, int B_MAX) · 61 test cases · 2 s / 256 MB per case