JOIN
Get Time

   Problem Statement  

 Problem Statement for BearEats

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 ints N, R, C, D, A_MAX, and B_MAX. As defined above, N is the number of cookies. The flavors of cookies are generated by the pseudocode below. Watch out for integer overflow when implementing it.



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.

 

Definition

    
Class:BearEats
Method:getDifference
Parameters:int, int, int, int, int, int
Returns:long
Method signature:long getDifference(int N, int R, int C, int D, int A_MAX, int B_MAX)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
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.
2)
    
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.
3)
    
200000
999998741
999997411
64592149
57
75
Returns: 462494

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2015 TopCoder Open Algorithm Round 3B - Division I, Level Two
       2015 TopCoder Open Algorithm Parallel Round 3B - Division I, Level Two