CircularParking | Topcoder Archive

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.
```
4
```
```
1
```
```
2
```
```
3
```
```
Returns: 4
```
The example from the problem statement.

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.