시간 제한메모리 제한제출정답맞힌 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB111100.000%

문제

You are participating in the Grand Kickstart Lucky Dip with many fantastic and amazing prizes (and some not so good ones)!

In this Lucky Dip, there is a bag with N items. The i-th item in the bag has value Vi. You will put your hand into the bag and draw one item at random; all items in the bag have an equal probability of being chosen. The organizers want contestants to feel that they have some element of choice, so after you draw an item, you can either keep it, or "redip" by returning it to the bag and drawing again. (Note that the returned item is now just as likely to be chosen as any of the other items in the bag.) You may only redip a maximum of K times. If you use K redips, you must keep the item that you draw on your (K + 1)-th draw.

If you play optimally to maximize the value of the item you will end the game with, what is the expected value of that item?

입력

The input starts with one line containing one integer T: the number of test cases. T test cases follow.

Each test case consists of two lines. The first line consists of two integers N and K: the number of items in the bag, and the maximum number of times you may redip. The second line consists of N integers Vi, each representing the value of the i-th item.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected value described above. Your answer will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer.

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ Vi ≤ 109.
  • 1 ≤ N ≤ 2 * 104.

Test Set 1 (10점)

시간 제한: 20 초

  • 0 ≤ K ≤ 1.

Test Set 2 (19점)

시간 제한: 60 초

  • 0 ≤ K ≤ 5 * 104.

예제 입력 1

5
4 0
1 2 3 4
3 1
1 10 1
3 15
80000 80000 80000
1 1
10
5 3
16 11 7 4 1

예제 출력 1

Case #1: 2.500000
Case #2: 6.000000
Case #3: 80000.000000
Case #4: 10.000000
Case #5: 12.358400

힌트

In Sample Case #1, you cannot redip, so the expected value is just the mean of the items in the bag which is (1 + 2 + 3 + 4) / 4 = 2.5.

In Sample Case #2, the best strategy is to keep the item of value 10 if you get it, and redip otherwise. The chance of getting that item (on either the first or second draw) is 1 - (2/3)2 = 5/9, hence the expected value is (5/9 * 10) + (4/9 * 1) = 6.

In Sample Case #3, since all the items have the same value, it does not matter how many times you redip and hence the expected value is 80000.

Note that cases #3 and #5 would not appear in the Small dataset.

채점 및 기타 정보

  • 예제는 채점하지 않는다.