← 返回题目列表

AtCoder · agc041_b

B. 投票评委

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

分数: 700 点

问题陈述

N 为即将举行的比赛提出问题。问题 i 的初始整数分数为 A_i 点。

M 评委们即将投票选出他们喜欢的问题。每位评委都会准确选择 V 问题,独立于其他法官, 并将每个选定问题的分数增加 1.

毕竟 M 评委投票,问题按照分数不升序排列,排名第一的 将选择 P 问题作为问题集。 分数相同的题目可以任意排序,这个顺序由主审决定。

给定的问题有多少 N 有机会被选为问题集吗?

约束

  • 2 \le N \le 10^5
  • 1 \le M \le 10^9
  • 1 \le V \le N - 1
  • 1 \le P \le N - 1
  • 0 \le A_i \le 10^9

输入

输入由标准输入按以下格式给出:

N M V P
A_1 A_2 ... A_N

输出

打印有机会被选择作为问题集的问题数。


示例输入 1

6 1 2 2
2 1 1 3 0 2

示例输出 1

5

如果唯一的法官投票给问题 2 和 5,分数将为 2 2 1 3 1 2。 问题集将包含问题 4 和问题之一 1, 2,或 6.

如果唯一的法官投票给问题 3 和 4,分数将为 2 1 2 4 0 2。 问题集将包含问题 4 和问题之一 1, 3,或 6.

因此,问题 1, 2, 3, 4,和 6 有机会被选为问题集。反之则没有办法解决问题 5 待选择。


示例输入 2

6 1 5 2
2 1 1 3 0 2

示例输出 2

3

只有问题 1, 4,和 6 有机会被选中。


示例输入 3

10 4 8 5
7 2 3 6 1 6 5 4 6 5

示例输出 3

8