← 返回题目列表

Codeforces · 1835/B

B. 彩票

中文机器翻译题面 查看原题

从 $$$1$$$ 到 $$$n$$$ 的整数索引 $$$n$$$ 人来参加抽奖。每个人都收到一张票,票上有一个从 $$$0$$$ 到 $$$m$$$ 的整数。

在彩票中,从 $$$0$$$ 到 $$$m$$$ 统一抽取一个称为目标的整数。与目标号码最接近的 $$$k$$$ 彩票(或更少,如果没有足够的参与者)被宣布为获胜者。如果出现平局,则指数较小者的彩票被宣布为获胜者。

Bytek决定参加抽奖。他知道所有先前参与者门票上的价值。他可以在票上选择他想要的任何值,但不幸的是,由于他是最后一个收到票的人,因此他的索引为整数 $$$n + 1$$$。

Bytek 想中彩票。因此,他想知道他应该选择什么才能最大限度地提高获胜的机会。他想知道最小的整数,以防有很多这样的整数。你的任务是找到它并计算他获胜的机会。

输入

在输入的第一行中,有整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^6$$$、$$$0 \leq m \leq 10^{18}$$$、$$$1 \leq k \leq 10^6$$$)。

在下面的行中,有 $$$n$$$ 个整数,中间用一个空格分隔,表示参与彩票的人收到的彩票上的号码。这些数字是从 $$$0$$$ 到 $$$m$$$ 范围内的整数。

输出

您应该在标准输出上输出两个由一个空格分隔的整数。第一个应该等于目标值的数量(从 $$$0$$$ 到 $$$m$$$),在抽签时 Baytek 获胜,前提是他选择了最佳彩票。第二个应该等于 Bytek 应该选择的整数,以最大化他赢得彩票的机会。

示例

输入 #1

3 6 2
1 4 5

输出 #1

4 2

输入 #2

7 7 1
2 4 7 3 0 1 6

输出 #2

1 5

注意

在第一个示例中,如果 Bytek 选择整数 $$$2$$$(最低最优值),则他将赢得 $$$4$$$ 目标值(即 $$$0, 1, 2, 3$$$)。如果他选择$$$3$$$,他也会在四种情况下获胜,但这不是最低的值。