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
250000
100000
1
2
3
4
5
Returns: 4903175879328122
1
12345
0
0
0
0
0
Returns: 0
247048
74815
775
58101
2215
4289
4
Returns: 4494207079030778
189755
95170
94
56300
12157
1
1724
Returns: 2233679807579043
68
95471
6
5
18
3
1
Returns: 92908
217457
99452
91
1907
21
22894
9
Returns: 2912522907445418
221263
14167
241
0
4646
1066
138
Returns: 3607112305721721
31
98105
2
13
1
4
3
Returns: 7219
105862
98763
12
565
7
6993
506
Returns: 332977611632304
2
85584
0
0
1
0
0
Returns: 0
194474
82547
1274
59014
4
7470
79201
Returns: 2316552974652654
31975
78163
3
5706
918
2
27297
Returns: 9035214447862
252
95851
0
0
6
2
87
Returns: 5125470
10
91265
2
4
1
7
6
Returns: 245
245467
96697
31948
40600
89
130229
657
Returns: 4335036196493915
293
99906
278
216
45
11
139
Returns: 6207669
244433
7665
0
2829
7101
38582
1718
Returns: 4793868686743427
241072
34971
2
46
7967
50
0
Returns: 4652139499750270
182
61737
53
0
4
1
37
Returns: 1612293
133750
4956
3
1
14856
604
235
Returns: 784202390201898
246183
23124
271
0
181243
11
2
Returns: 4793116767444409
109121
75801
10
3932
165
2
2
Returns: 390524434813733
5
74705
0
4
0
1
1
Returns: 14
244241
92269
46416
227
6
112420
7
Returns: 4359062346101988
244766
79771
141119
484
628
10
215
Returns: 4635870637586942
244826
90620
183
63
18921
2143
7
Returns: 4335266746798069
246783
91411
46
77237
120492
417
1267
Returns: 4512028957065486
977
91924
71
827
3
419
47
Returns: 241518660
53
66108
26
31
2
3
0
Returns: 36428
244659
72469
6029
15634
1
14
11258
Returns: 4337867485660450
1
69754
0
0
0
0
0
Returns: 0
246009
94008
28524
59
30
1
11990
Returns: 4361061816310132
246926
98038
57
32
127
33537
104278
Returns: 4340130008713887
80321
81881
70
45
30835
29488
14
Returns: 165245098429444
248587
71532
6
58052
167
1
1
Returns: 4529092592519048
246132
30275
166015
77
13
1
28
Returns: 4968245870297741
248721
93946
977
49982
6
130
100613
Returns: 4814330187573952
230616
95955
11
0
4
4070
42
Returns: 4030879432433551
249138
99009
125
30373
1
105
47186
Returns: 4544300560126022
35580
92814
53
0
25
0
29
Returns: 14831475814573
249134
90992
62
34
81285
0
776
Returns: 5104208022593184
25837
95878
16680
245
11233
6
1978
Returns: 4508344654470
17457
84087
2
1425
82
63
306
Returns: 1535355603610
240619
98293
165
223
13
114072
10
Returns: 3999946793460884
149631
88893
28
0
7
18
5
Returns: 922377888884328
2
92964
0
1
0
1
1
Returns: 0
6
97899
0
1
1
4
2
Returns: 38
243034
97422
2
1808
63
3
35
Returns: 4384879104161332
711
1663
14
5
56
246
20
Returns: 107790517
1742
90772
10
17
0
1455
0
Returns: 1694356467
771
54316
15
29
0
10
0
Returns: 118825162
51
94573
26
6
0
6
44
Returns: 36563
752
7856
5
1
1
382
37
Returns: 128784161
152213
98157
0
766
53
0
2214
Returns: 918648921038949
90590
81823
1
5
3
2162
6
Returns: 206732589699610
203848
35071
15
82231
400
1
1818
Returns: 2804817463800502
244255
62928
226
22
3727
1
19543
Returns: 4816087715662444
217717
91395
149432
1
208
4827
50
Returns: 2950572468004540
615
97910
18
36
18
18
45
Returns: 68416976
187508
98075
127069
2204
87775
35
606
Returns: 1928453958148492
211215
53295
126
48
3289
176560
173079
Returns: 2972611381602011
240691
93243
152705
94415
66144
42798
123
Returns: 4023105181355479
248440
99877
28
431
460
19289
401
Returns: 4744001175754646
156996
95240
54308
968
34
0
31591
Returns: 1288796032233156
87616
91124
6
49
25825
726
45
Returns: 190293804881611
22
48660
4
0
4
2
11
Returns: 2420
67003
92285
103
1962
5
15
14907
Returns: 78642491740616
248316
23005
5012
6
2821
115
1
Returns: 4894863885870981
1747
36882
0
0
1
1
0
Returns: 1774235730
501
91349
45
4
0
1
7
Returns: 31258362
94552
94813
8053
488
906
53233
6794
Returns: 244644426267435
242452
95872
79
297
27073
6
0
Returns: 4292331797293929
250000
100000
212343
212343
212343
212343
212343
Returns: 4909843643856173
250000
100000
249999
249999
249999
249999
249999
Returns: 5208270833999997
249999
100000
90099
90000
90001
90002
90003
Returns: 5203455154289545