All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Benny and Candies
Tag(s):

Algorithms, Easy-Medium, Easy-Medium, Greedy

Problem
Editorial
Analytics

One day Benny came up with an excellent idea to become a business-pig! She knows that almost everyone likes candies.

Benny knows about that somewhere on the Earth candy-stock exists. She knows that at the $$i$$-th of $$n$$ days she can buy or sell sweet called "Korovka", if she wants. The price for buying or selling the sweet at the $$i$$-th day equals to $$c_i$$.

Unfortunately, Benny is not allowed to have more than one candy at some moment of time according to candy-stock rules. She firstly has to sell the candy and then may buy the new one.

Please, note, that at one day Benny could firstly sell the candy and then buy the new one.

From the beginning she has a vary big budget. Benny wants to make the maximal possible profit in case of making such business for $$n$$ consecutive days and not breaking any candy-stock rules.

Array $$c$$ is generated in the following way:

$$$x_0 = 0$$$ $$$x_i = ((x_{i-1} \bmod M) \cdot a + b) \bmod 2^{32}$$$

$$$c_i = \left\lfloor \frac{x_i}{2^{8}} \right\rfloor$$$

Input format

The first line contains two integers: $$n$$ and $$M$$.

The second line contains two integers: $$a$$ and $$b$$.

Constraints

$$2 \leq n \leq 10^7$$

$$1 \leq M \leq 2^{30}$$

$$1 \leq a, b \leq 10^9$$

Output format

In a single line output the maximum profit Benny can get.

SAMPLE INPUT
5 100500
1 1024
SAMPLE OUTPUT
16
Explanation

The array $$c$$ will look like {4, 8, 12, 16, 20}. Let B be buy and S be sale.

BSBSBSBS.

If you use the strategy above you will get the maximum profit.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications