问题 4664 --轮流去打怪

4664: 轮流去打怪★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 22  解决: 15
[提交][状态][命题人:]

题目描述

n 个怪物站成一排,编号从 1 n 。第i个怪物有 Hi 点生命值。你的攻击力为 a ,你的对手的攻击力为 b 。

你和你的对手只能轮流对同一个怪物造成伤害。如果怪物的生命值小于或等于0,则认为它已经死亡,只有当前怪物死亡,你们才可以去挑战其他怪物。

如果怪兽死于你的最后一次进攻,你加一分,否则没人加分。

你有一种魔法可以迫使你的对手跳过一次攻击。你最多可以使用这个魔法k(例如,如果有两个怪物且k4,则你可以在第一个怪物上使用此技术2次,在第二个怪上使用此技术1次,但不能在第一个怪物上使用此技术2次,在第二个怪物上使用此技术3)

问如果采取最佳策略,你能获得多少分。

输入

输入的第一行包含四个整数nabk,分别为怪物的数量,你的攻击力,对手的攻击力和你可以使用魔法的次数(1n2*1051a,b,k109)。 输入的第二行包含n个整数H1H2,…,Hn1Hi109),其中Hi是第i个怪物的生命值。

输出

打印一个整数-如果您使用最佳策略,您可以获得的最多分数。

样例输入
Copy
6 2 3 3
7 10 50 12 1 8
样例输出
Copy
5

提示

样例2输入

1 1 100 99
100

样例2输出

1

样例3输入

7 4 2 1
1 3 5 4 2 7 6

样例3输出

6

来源

[提交][状态]