EllysSuperMario | Topcoder Archive

Problem Statement

Elly plays a modified version of Super Mario. In the game the player must pass over N cells, potentially stepping on some of them. The girl starts to the left of the leftmost cell and her goal is to go beyond the rightmost one. At each move she can jump between 1 and K cells to the right of her current position. Each cell has associated price C_i. When the player steps on a cell she must pay this amount of coins. The goal of the game is to minimize the total amount of coins paid.

Imagine a level of this game with N = 6 cells with respective prices (4, 7, 6, 1, 8, 11) and maximal jump K = 2. In the first move the girl can jump on the first or second cell (paying, respectively, 4 or 7 coins). Elly would chose the second one, paying more, but going further to the right. Her next jump should be to the fourth cell (paying one more coin); then just a short jump to the fifth cell (paying 8 coins); and finally jumping outside the board. The total amount of coins she pays is 7 + 1 + 8 = 16, which is also the minimum that can be achieved for this level.

You want to help Elly by writing a program that finds the path with minimal cost. The girl has provided you with the information about the level she is currently playing. This includes the int N and int K, as well as four ints F, A, B, and M. The leftmost cell of the level has price F. Each consecutive cell is generated by the formula C_i = (C_i-1 * A + B) % M, where % denotes the modulo operation. Return the minimal amount of coins that must be paid in order to reach the right end of the level.

Definition

Class:: EllysSuperMario
Method:: getMin
Parameters:: int, int, int, int, int, int
Returns:: long
Method signature:: long getMin(int N, int K, int F, int A, int B, int M)
(be sure your method is public)

Constraints

N will be between 1 and 10,000,000, inclusive.
K will be between 1 and 1,000,000, inclusive.
M will be between 1 and 1,000,000,007, inclusive.
F, A, and B will be between 0 and M-1, inclusive.

Examples

```
6
```
```
2
```
```
4
```
```
5
```
```
3
```
```
16
```
```
Returns: 16
```
This is the example from the problem statement - the generated numbers are (4, 7, 6, 1, 8, 11) and the maximal jump is 2 cells.
```
10
```
```
13
```
```
6
```
```
6
```
```
6
```
```
13
```
```
Returns: 0
```
When K is greater than N, Elly can simply jump over all of the cells for free.
```
15
```
```
5
```
```
5
```
```
5
```
```
5
```
```
25
```
```
Returns: 15
```
Sometimes the game levels can be a bit boring.
```
20
```
```
4
```
```
133
```
```
61
```
```
177
```
```
240
```
```
Returns: 327
```

12345678

Returns: 18125856

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)2024, Topcoder, Inc. All rights reserved.