AqaAsadiMinimizes | Topcoder Archive

Problem Statement

Aqa Asadi is a kind teacher who puts a lot of effort into helping students grow and make friends.

N students stand in a line. They are numbered 0 through N-1, in order. Student i is A[i] seconds old.

Aqa Asadi came up with a formula that measures how difficult it is for two students to become friends: for students i and j, the difficulty is |A[j] - A[i]| / |j - i|. In the formula, |x| denotes the absolute value of x.

Find the pair of students with the smallest difficulty to form a friendship, and return that difficulty.

Use the following pseudocode for generating the array A[0..N-1]:

for i = 0 to N-1:
    if i &lt; length(P):
        A[i] = P[i]
    if i == length(P):
        A[i] = B0
    if i &gt; length(P):
        A[i] = (A[i-1] * X + Y) modulo 1000000007

Definition

Class:: AqaAsadiMinimizes
Method:: getMin
Parameters:: int[], int, int, int, int
Returns:: double
Method signature:: double getMin(int[] P, int B0, int X, int Y, int N)
(be sure your method is public)

Notes

The returned value will be accepted if its relative or absolute error does not exceed 1e-9.

Constraints

N will be between 2 and 500,000, inclusive.
P will have between 0 and N elements, inclusive.
P will have at most 100 elements.
B0, X, Y, and all elements of P will be between 0 and 1,000,000,006, inclusive.

Examples

```
{11, 0, 30, 20, 1000}
```
```
0
```
```
0
```
```
0
```
```
5
```
```
Returns: 3.0
```
The best pair are the students i=0 and j=3, their difficulty of forming a friendship is |20 - 11| / |3 - 0| = 9/3 = 3.

{47, 1, 10, 3, 2}

Returns: 0.3333333333333333

Students i=1 and j=4 are the best choice here.

```
{123456}
```
```
234567890
```
```
345678
```
```
456789
```
```
10
```
```
Returns: 8333191.571428572
```
A = {123456, 234567890, 958968621, 353106369, 103025544, 664206330, 514591322, 898217931, 176235549, 752137571}

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.