Zonal Computing Olympiad 2010, 12 Dec 2009
10:00 am–1:00 pm IST
Problem 1 : Sequence game
You are given a sequence of N positive integers i1, i2, …, iN. In addition, you are given a starting integer b and lower and upper integer limits min and max, respectively. Note that 0 ≤ min ≤ b ≤ max always.
The sequence game is played as follows. Initially, your score is b. In step 1, you can either add i1 to b or subtract i1 from b to get a new score b1. In step 2, you update b1 by adding or subtracting i2 to get a new score b2. Proceeding in this way, in step j, you update bj-1 by adding or subtracting ij to get a new score bj. The rule is that each score bj should always lie between min and max, inclusive: that is, for each j, 1 ≤ j ≤ N, it should be the case that min ≤ bj ≤ max. Your final score is bN, after using the last number in the sequence.
Your aim is to maximise your final score while playing according to the rules. If there is no way to complete all N steps without going outside the bounds min and max, your score is -1.
For example, suppose the sequence of numbers you have is [2,3,4], b is 5, min is 0 and max is 8. After step 1, the score can be 3 or 7. After step 2, the score can be 0, 4, or 6. A score of 10 is not allowed since max is 8. After step 3, the score can be 0, 2, 4, or 8. Thus, in this game, the maximum score you can obtain at the end of the sequence is 8.
Input format
The first line of the input contains four integers N, b, min and max, whose meaning is as explained above. The second line of input contains N space separated integers, the sequence over which the game is played.
Output format
Your output should be a single line consisting of one integer, the maximum final score that you can achieve.
Testdata
In all cases, N ≤ 103 and 0 ≤ min ≤ b ≤ max ≤ 103.
Sample Input
3 5 0 8 2 3 4
Sample Output
8
Copyright (c) IARCS 2003-2024; Last Updated: 10 Sep 2010