LunchLine
SRM 809 · 2021-07-12 · by misof
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
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.
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
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LunchLine with a public method long long simulate(int N, int M, int A, int B, int C, int D, int E) · 80 test cases · 2 s / 256 MB per case