← 返回题目列表

AtCoder · ijpc2015_e

B. 卡牌游戏

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

問題文

Snuke 和 Sumeke 决定使用编号卡和硬币玩以下游戏。

首先,Snuke 一张写有 T 的卡片,并且 K 硬币,Sumeke先生给了一张卡片。 我有 N 。
这个游戏是 分为 N 轮,Sumeke每轮执行一次以下步骤。

  • Sumeke先生选择了一张他尚未向Snuke展示的牌并向他展示。这张卡上写的号码 A 。 上线
  • Snuke 持有的卡片上写的号码 B 那么,Snuke-kun是Sumeke-san的。|A-B| 受到伤害。
  • 当 Snuke 有金币时,给 Sumeke 一枚金币。 A 卡 要么用它交换一张 B 卡,要么不给金币什么也不做。
在这个游戏中,Snuke 希望最小化他在每轮中受到的最大伤害。

所以,Snuke君发现了Sumeke-san的策略,而Sumeke-san并不关心Snuke-kun的行动。 i 写入的值 我确信他会打出 A_i 牌。

求 Snuke 在每轮中受到的最小可能最大伤害。
然而,每回合结束后,Sumeke 都会恢复 Snuke 的伤害。


入力

输入将以以下格式从标准输入提供。

N T K
A_1 A_2 ... A_N
  • 第一行是轮数。 N(1≦N≦100,000)您拥有的第一张卡片上写的号码 T(1≦T≦10^{9}), 硬币数量 K(1≦K≦N) 。 来自行
  • 下一行是 给定N 数字,i Sumeke 作为整数 i(1≦i≦N) 第一次玩时写在卡上的号码 A_{i}(1≦A_{i}≦10^{9}) 。 来自行

配点

这个问题有部分要点。作为附加约束, 如果您在满足 N=K 的情况下解决了此问题,您将获得20分。

出力

在一行中,打印 Snuke 在每一轮中受到的最小可能最大伤害。 在末尾插入换行符。

入力例1

5 1 1
1 2 3 4 5

出力例1

2

入力例2

8 9 3
11 4 5 14 19 19 8 10

出力例2

6