AqaAsadiMinimizes
SRM 787 · 2020-06-17 · by a.poorakhavan
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 < length(P):
A[i] = P[i]
if i == length(P):
A[i] = B0
if i > length(P):
A[i] = (A[i-1] * X + Y) modulo 1000000007
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.
{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}
0
0
0
5
Returns: 0.3333333333333333
Students i=1 and j=4 are the best choice here.
{}
1
1
1
500000
Returns: 1.0
{}
1
1
0
500000
Returns: 0.0
{922775522, 652913942, 199433255, 787328317, 969451951, 797384855, 334639666, 226448392, 822018246, 29395346, 802722515, 918324184, 274902223, 571486952, 802538779, 483667018, 546156066, 547778296, 77065150, 564653974, 190994759, 893170529, 389474108, 250200939, 85138230, 866155174, 437059941, 74418143, 20635319, 729041165, 492812116, 789041310, 80788342, 657551148, 83578153, 337344217, 358755901, 279590855, 586625340, 346220583, 656234093, 784279361, 209417013, 627709215, 531085527, 766358728, 81584560, 139917860, 539897052, 902664892, 22331841, 887434354, 972770284, 81553842, 656642132, 776167496, 800880463, 144114994, 803958154, 325218585, 629074313, 995579032, 915143235, 136723743, 296097141, 488631682, 126018575, 555421745, 695694510, 959479412, 370293222, 750454906, 547290356, 764543353, 345043918, 539777544, 935869071, 764495018, 21523167, 608660880, 226830175, 593435378, 581910485, 554000981, 981755478, 230975814, 482047251, 896754453, 484890024, 531623992, 651071307, 852013294, 415167693, 645121012, 905870749, 711116633, 579307283, 819164963, 286037053, 893339753}
21127135
944574999
717701653
100
Returns: 2169.5384615384614
{123456}
234567890
345678
456789
10
Returns: 8333191.571428572
A = {123456, 234567890, 958968621, 353106369, 103025544, 664206330, 514591322, 898217931, 176235549, 752137571}
Submissions are judged against all 74 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AqaAsadiMinimizes with a public method double getMin(vector<int> P, int B0, int X, int Y, int N) · 74 test cases · 2 s / 256 MB per case