← 返回题目列表

Codeforces · 1211/D

D. 团队

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

桌上有 $$$n$$$ 名保龄球玩家,第 $$$i$$$ 玩家的评级等于 $$$r_i$$$。按照以下方式组成最大数量的团队:

- 每个玩家最多属于一个团队;
- 每个团队恰好包含 $$$a+b$$$ 玩家;
- 每个团队包含一组具有相同等级的 $$$a$$$ 玩家和一组具有相同等级的 $$$b$$$ 玩家,该等级必须比第一组中玩家的等级大 $$$k$$$ 倍。

例如,如果 $$$n=12$$$、$$$r=[1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 6, 6]$$$、$$$a=1$$$、$$$b=2$$$、$$$k=2$$$,则可以组成两个评分为 $$$[1, 2, 2]$$$ 和一支评级为 $$$[3, 6, 6]$$$ 的球队。因此,团队的最大数量为 $$$3$$$。

根据给定的 $$$n、r_1 \dots r_n、a、b$$$ 和 $$$k$$$ 找到最大团队数量,以根据给定的要求组成。

输入

输入的第一行包含四个整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le n,a,b \le 3\cdot10^5$$$, $$$2 \le k \le 1000$$$)。第二行包含玩家评级的序列 - 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^6$$$)。

输出

仅打印一个整数 — 由 $$$n$$$ 给定玩家组成的最大团队数。

示例

输入 #1

12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6

输出 #1

3

输入 #2

14 1 1 3
3 3 1 1 9 9 2 3 6 6 3 18 3 18

输出 #2

6

输入 #3

1 2 3 10
1000000

输出 #3

0