Lucky Draw 是如何解决的呢

In the Lucky village, people are crazy on a game called Lucky Draw. In this game, N players stand in a line, and each one is assigned an integer number. Then, the village master would randomly choose K continuous players. Among these K players, the one who has the largest number will win the first prize of A dollars. Also, the one with the second smallest number will win the second prize of B dollars. Different players may have same numbers. As an agreement, only the rightmost player who has the largest number owns the first prize, and the leftmost player who has the second smallest number owns the second prize. Note that the second smallest number should be greater than the smallest number. Therefore, if all of these K players have the same number, no one will win the second prize.

A big problem in this game is about fairness. Some players may have much more chance to win prizes than others. So, the village master wants to know how fair the game is. You should tell the village master how many players have the opportunity to win the prize. In addition, you need to calculate the variance of the expected prize moneys of these potential prize winners.

The first line contains four integers, N, K, A, B, as described before. (1 ≤ K ≤ N ≤ 1000000, 1 ≤ A, B ≤ 1000).

The second line contains N integers, indicate the numbers assigned to those players, listed from left to right. The numbers are guaranteed to fit in 32-bit signed integers.
Output only one line containing an integer M and a real number V, separated by a single space. M is the number of players who have any chance to win the prize money. V is the variance of the expected prize money of these M players, rounded to four digits after the decimal point.
6 3 1 2
1 2 1 3 3 3
4 0.1719

Csdn user default icon