All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

The lone wolf dies, but the pack survives
No tags

Nymeria wants to join a wolf pack to protect herself during the winter that is fast approaching. There's a wolf pack in Riverlands that allows wolves to join their pack if they are able to solve a question. Help Nymeria join the pack by solving the question.

You are provided with an array of N integers and a number Y, and asked to perform exactly D operations on it. Operations are such that you have to :

1. First subtract an integer X from each element of the array

2. Check if any of them becomes negative or zero then discard them

3. Add an integer Y to the remaining ones

Repeat these 3 steps D times such that you are left with an empty array at last.

Your task is to choose the smallest possible integer value of X to perform the above mentioned operations on the array.



1 <= N <= 106

1 <= Ai, Y, D <= 106


First line of each input dataset will contain 3 space separated integers N, D and Y.
Next line will contain N space separated array elements.


Output the smallest possible value X can take.


5 2 2
2 1 5 3 6

Here we have D = 2 and Y = 2

Initially we have the array as : 2 1 5 3 6 

suppose we choose X = 4

After 1st operation we have :

-2  -3  1  -1  2  => discarding 1st, 2nd and 4th element => 1  2 => add Y to it => 3  4 

After 2nd operation we are left with :

-1  0 => discard all  => empty array 

So X = 4 is a possible answer.

Check it youself for more values of X, you will see that it is the smallest possible value for X.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications