Problem Statement
This problem is about simulating how N cars park along a circular street.
There is a long circular one-way road. Along the road there are N parking spots, numbered from 0 to N-1 in order. As you drive along the road, parking spot numbers increase. (As the road is circular, after N-1 you get back to 0.)
Initially, all parking spots are empty. N cars arrive to the circular road and park there. The cars arrive one at a time: the next car always arrives only after the previous one has parked.
The cars are numbered from 0 to N-1 in the order in which they arrive. The numbering of cars is unrelated to the numbering of parking spots.
For each i from 0 to N-1, inclusive: Car i will arrive to the circular road in such a place that the first parking spot it encounters is the parking spot P[i] = (A*i*i + B*i + C) modulo N.
Each car drives along the road until it finds an empty parking spot. Once it finds an empty parking spot, it parks there.
For example, suppose we have N = 4 and (A,B,C)=(1,2,3). Car 0 will park at spot P[0] = 3, car 1 will park at spot P[1] = 2, car 2 will appear next to the occupied parking spot P[2] = 3, drive past it and park at spot 0, and finally car 3 will appear at P[3] = 2, drive past occupied spots 2, 3, and 0, and park at the final free spot 1.
Each time a car encounters an occupied parking spot, a collision occurs. For example, in the scenario described above the cars produce a total of 0 + 0 + 1 + 3 = 4 collisions. We don't like collisions, as they cause delays.
Calculate and return the total number of collisions that will happen while our N cars park.
Definition
- Class:
- CircularParking
- Method:
- park
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long park(int N, int A, int B, int C)
- (be sure your method is public)
Notes
- It should be obvious that the correct answer always fits into a signed 64-bit integer.
- Watch out for integer overflows when computing the value "(A*i*i + B*i + C) modulo N".
Constraints
- N will be between 3 and 250,000, inclusive.
- A will be between 0 and N-1, inclusive.
- B will be between 0 and N-1, inclusive.
- C will be between 0 and N-1, inclusive.
Examples
47
0
1
0
Returns: 0
For each i, car i arrives at the parking spot i, and as it is empty, it parks there. No collisions.
47
0
0
42
Returns: 1081
Each car arrives at the parking spot 42. Car i will have i collisions before it parks on the spot (42+i) modulo 47.
30
1
1
1
Returns: 175
Car i starts looking for an empty parking spot at the parking spot (i*i + i + 1) modulo 30. There will be some collisions. E.g., eight of the 30 cars will start at the parking spot number 13.
250000
2352
32652
199975
Returns: 93375000
250000
0
0
248987
Returns: 31249875000
250000
0
249999
23565
Returns: 0
250000
0
50000
2352
Returns: 6249875000
250000
0
475
23523
Returns: 3000000
250000
0
7000
23362
Returns: 124875000
250000
0
70000
0
Returns: 1249875000
249997
0
0
0
Returns: 31249125006
223058
0
112770
149629
Returns: 111529
222509
222508
134334
102869
Returns: 81438294
240341
0
208426
172655
Returns: 0
201550
0
164
126236
Returns: 100775
247438
0
240491
148784
Returns: 0
228029
1
62322
115925
Returns: 78213947
215862
0
147048
187887
Returns: 539655
245062
245061
157542
146221
Returns: 78909964
237689
1
0
32898
Returns: 70593633
221884
0
95115
133249
Returns: 1775072
235397
235396
25453
183293
Returns: 91569433
221945
1
123477
202656
Returns: 88334110
227306
227305
176909
202620
Returns: 111493593
215661
215660
0
126863
Returns: 69370955
220460
68223
191420
158949
Returns: 97663780
207466
1
99579
66358
Returns: 133296905
239552
1
0
44641
Returns: 192360256
235847
0
19557
134017
Returns: 0
240797
205086
210205
95834
Returns: 100893943
249753
0
159328
235718
Returns: 0
242224
239712
185646
217456
Returns: 30156888
201457
1
55407
113151
Returns: 70308493
245337
1
46314
241425
Returns: 95272535
213020
1
25799
191475
Returns: 84462430
237330
237329
138255
28333
Returns: 119416545
217489
120
171081
108545
Returns: 60026964
204401
204400
5432
10932
Returns: 61320300
209203
1
193762
52729
Returns: 62970103
232420
147747
0
182199
Returns: 135268440
204839
1
39470
166599
Returns: 132530833
203059
1
0
99281
Returns: 54216753
208070
0
23223
14127
Returns: 0
235904
235903
62683
144160
Returns: 13328576
237995
237994
162263
147576
Returns: 97339955
232194
232193
0
30040
Returns: 82815860
227097
92733
79380
156673
Returns: 156696930
209152
0
133136
120917
Returns: 1568640
242791
215920
4686
212251
Returns: 90561043
236957
0
204895
205454
Returns: 0
246186
131701
29918
92324
Returns: 113819994
221699
1
0
154068
Returns: 62740817
206434
120726
0
146852
Returns: 83915421
212405
212404
10718
142148
Returns: 76040990
231633
17949
189378
230476
Returns: 177662511
234135
140814
195122
151640
Returns: 29032740
220427
201849
178993
191984
Returns: 75386034
241452
0
26917
106189
Returns: 0
221807
221806
28521
163165
Returns: 50350189
248757
94512
13171
152786
Returns: 66666876
203701
166184
70231
55210
Returns: 60091795
218987
1
121897
116718
Returns: 43578413
228865
228864
0
40704
Returns: 90630540
238029
163
7215
227061
Returns: 131233322
229976
160973
213552
77060
Returns: 28057072
206717
206716
32466
110909
Returns: 87648008
222063
111674
61474
82048
Returns: 104295589
236358
0
159616
224351
Returns: 118179
238968
161739
146358
178921
Returns: 360124776
245999
213515
11218
160690
Returns: 189173231
211892
0
127127
15799
Returns: 0
4
1
2
3
Returns: 4
The example from the problem statement.
250000
0
0
42
Returns: 31249875000
250000
59467
1
1
Returns: 46625000
250000
0
0
0
Returns: 31249875000
250000
0
0
240000
Returns: 31249875000
250000
249000
249000
249000
Returns: 4249875000
250000
3
2
2
Returns: 218000000
25000
4567
4567
1234
Returns: 2162500
250000
1
0
249999
Returns: 218000000
250000
249999
249999
249999
Returns: 46625000
250000
25000
25000
25000
Returns: 18749875000