Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Expected Difference
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 1440Accepted: 380

Description

Given n distinct integer numbers A = { A1, A2, …, An } and an integer m, then choose m distinct elements B = { B1, B2, …, Bm } randomly from A. You are to calculate the expected difference between the largest and smallest number of B.

For example, consider the case where n = 4, m = 2, and A = { 1, 2, 3, 4 }. It has 12 probability to obtain a difference of 1, 13 probability of 2 and 16 probability of 3. So the answer is 12 × 1 + 13 × 2 + 16 × 3, which is equal to 53 ≈ 1.667.

Input

The input contains multiple test cases.

Each test case contains consists of two lines. The first line gives the integers n (2 ≤ n ≤ 50 000) and m (2 ≤ mn). The second line gives n distinct integers A1, A2, …, An. (0 ≤ Ai ≤ 65 536), which will be sorted in increasing order.

A pair of zeroes indicates the end of the input and should not be processed.

Output

Output the answer of each test case on a separate line with the fraction rounded to 3 decimal places.

Sample Input

2 2
1 2
3 2
1 2 3
4 2
1 2 3 4
4 3
2 3 8 9
0 0

Sample Output

1.000
1.333
1.667
6.500

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator