310456: CF1836D. Lottery
Description
$n$ people indexed with integers from $1$ to $n$ came to take part in a lottery. Each received a ticket with an integer from $0$ to $m$.
In a lottery, one integer called target is drawn uniformly from $0$ to $m$. $k$ tickets (or less, if there are not enough participants) with the closest numbers to the target are declared the winners. In case of a draw, a ticket belonging to the person with a smaller index is declared a winner.
Bytek decided to take part in the lottery. He knows the values on the tickets of all previous participants. He can pick whatever value he wants on his ticket, but unfortunately, as he is the last one to receive it, he is indexed with an integer $n + 1$.
Bytek wants to win the lottery. Thus, he wants to know what he should pick to maximize the chance of winning. He wants to know the smallest integer in case there are many such integers. Your task is to find it and calculate his chance of winning.
InputIn the first line of the input, there are the integers $n$, $m$, and $k$ ($1 \leq n \leq 10^6$, $0 \leq m \leq 10^{18}$, $1 \leq k \leq 10^6$).
In the following line, there are $n$ integers separated by a single space, denoting the numbers on tickets received by people participating in a lottery. These numbers are integers in the range from $0$ to $m$.
OutputYou should output two integers separated by a single space on the standard output. The first should be equal to the number of target values (from $0$ to $m$), upon drawing which Baytek wins, given that he chooses his ticket optimally. The second should be equal to the integer Bytek should pick to maximize his chance of winning the lottery.
ExamplesInput3 6 2 1 4 5Output
4 2Input
7 7 1 2 4 7 3 0 1 6Output
1 5Note
In the first example, Bytek wins for $4$ target values (namely $0, 1, 2, 3$) if he chooses integer $2$, which is the lowest optimal value. If he chooses $3$, he also wins in four cases, but it is not the lowest value.
Input
Output
这是一个关于彩票的问题。有n个人参与彩票，每个人获得一张0到m之间的整数票。彩票的获胜方式是，从0到m中均匀抽取一个整数作为目标值，与目标值最接近的k张票（如果参与者不足k人，则取实际人数）的持有者获胜。如果有多张票与目标值相同接近，则索引值较小的人获胜。Bytek是最后一个参与者，他的索引值是n+1。Bytek想要赢得彩票，他需要知道选择哪个数值的票才能最大化他获胜的机会。如果有多个这样的数值，他想知道最小的那个是什么，并计算他获胜的概率。
输入输出数据格式：
输入：
第一行包含三个整数n、m和k（1≤n≤10^6，0≤m≤10^18，1≤k≤10^6）。
第二行包含n个由单个空格分隔的整数，表示参与彩票的人收到的票上的数字。这些数字是0到m之间的整数。
输出：
在标准输出上输出两个由单个空格分隔的整数。第一个数应该是Bytek选择最佳票时，他获胜的目标值数量（从0到m）。第二个数应该是Bytek为了最大化获胜机会应该选择的整数。题目大意： 这是一个关于彩票的问题。有n个人参与彩票，每个人获得一张0到m之间的整数票。彩票的获胜方式是，从0到m中均匀抽取一个整数作为目标值，与目标值最接近的k张票（如果参与者不足k人，则取实际人数）的持有者获胜。如果有多张票与目标值相同接近，则索引值较小的人获胜。Bytek是最后一个参与者，他的索引值是n+1。Bytek想要赢得彩票，他需要知道选择哪个数值的票才能最大化他获胜的机会。如果有多个这样的数值，他想知道最小的那个是什么，并计算他获胜的概率。 输入输出数据格式： 输入： 第一行包含三个整数n、m和k（1≤n≤10^6，0≤m≤10^18，1≤k≤10^6）。 第二行包含n个由单个空格分隔的整数，表示参与彩票的人收到的票上的数字。这些数字是0到m之间的整数。 输出： 在标准输出上输出两个由单个空格分隔的整数。第一个数应该是Bytek选择最佳票时，他获胜的目标值数量（从0到m）。第二个数应该是Bytek为了最大化获胜机会应该选择的整数。