Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Walking Down The Road

By kitorp · Limits 1s, 512 MB

There is an M meter long road with the leftmost point of the road being the 0 meter point and the right most point being the M meter point. N people are standing at different points on the road. Akina is a great problem solver. He likes to solve problems that are related to real life. Akina is thinking if the N peoples wanted to meet at certain point and they will just walk straight to that point from their position. If X is point where they can meet such that the summation of the distances each has to walk is minimum is called “Fuchka” point. Suppose a point can contain infinitely many people.
You are given a similar problem. Suppose you have to say a random point between 0 to M. What is the probability of the random point being the “Fuchka” point?


First line will contain an integer T (1 ≤ T ≤ 5), the number of test case. Then for each case There will be two lines. First line will contain two integers N and M; (1 < N ≤ 100000) and (N ≤ M ≤ 2000000) and N is even.
The next line will contain N number of integers the value of which will be between 0 to M inclusively. These points are the position of the people. No two points will be same.


For each case output a real number, the probability of the point being Fuchka point in a line.Error less then .000001 will be acceptable.


4 4
1 2 3 4
2 6
0 6



70% Solution Ratio

lexuananEarliest, Aug '17

experimenterFastest, 0.1s

lexuananLightest, 524 kB

mdvirusShortest, 311B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.