LunchLine | Topcoder Archive

Problem Statement

N kids are waiting in the line for lunch. The kids are numbered from 0 to N-1 in the order in which they are currently standing, with kid 0 being the one who would get lunch first.

The lunch lady hasn't started giving out lunch yet, and the kids are restless. However, each time someone misbehaves, Mrs. Trunchbull (the teacher in charge of the dining hall today) sends them to the very end of the line as a punishment.

You are given N and a sequence of M events. Events are numbered from 0 to M-1 in chronological order. In event i kid number K[i] is sent to the end of the line.

Compute the sequence F[0], ..., F[N-1] of numbers the kids in the queue have at the end. Return the value sum( i*F[i] ).

In order to keep the input size small, the sequence K of kids sent back is pseudorandom. Please use the following code to generate it:

if M > 0: K[0] = A
if M > 1: K[1] = B
for i = 2 to M-1: K[i] = (C*K[i-1] + D*K[i-2] + E) mod N

Definition

Class:: LunchLine
Method:: simulate
Parameters:: int, int, int, int, int, int, int
Returns:: long
Method signature:: long simulate(int N, int M, int A, int B, int C, int D, int E)
(be sure your method is public)

Notes

Watch out for integer overflows when generating K: 64-bit integers are needed for the intermediate values.

Constraints

N will be between 1 and 250,000, inclusive.
M will be between 0 and 100,000, inclusive.
A, B, C, D, E will be between 0 and N-1, inclusive.

Examples

```
250000
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
Returns: 5208302083375000
```
Nobody gets sent back, so the kids are still in the order 0, 1, 2, ... and the return value is sum(i^2) where i goes from 0 to N-1, inclusive.
```
10
```
```
5
```
```
2
```
```
3
```
```
1
```
```
0
```
```
1
```
```
Returns: 225
```
The sequence of kids sent back is {2, 3, 4, 5, 6}. Thus, in the end the line looks as follows: {0, 1, 7, 8, 9, 2, 3, 4, 5, 6}.
```
10
```
```
5
```
```
2
```
```
4
```
```
1
```
```
0
```
```
2
```
```
Returns: 210
```
Kids sent back: {2, 4, 6, 8, 0}. Final line: {1, 3, 5, 7, 9, 2, 4, 6, 8, 0}.
```
10
```
```
100000
```
```
4
```
```
7
```
```
0
```
```
0
```
```
3
```
```
Returns: 249
```
Kids sent back: {4, 7, 3, 3, 3, ...}. Final line: {0, 1, 2, 5, 6, 8, 9, 4, 7, 3}.
```
11
```
```
30
```
```
4
```
```
7
```
```
1
```
```
2
```
```
3
```
```
Returns: 229
```

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.