Ralph là một người rất thích đập đá. Còn trái ngược với Ralph là Felix - một tay chơi đá thực thụ, lại có sở thích dán đá.
Vì có sở thích trái ngược, Ralph đã thách thức Felix tham gia trò chơi đập-dán đá với mình.
Ralph là người đập còn Felix sẽ là người dán. 2 người chơi lần lượt, Ralph là người chơi
trước.
- Có ~n~ cục đá, cục thứ ~i~ ban đầu có độ bền bằng ~D_i~.
- Trong quá trình đập, Raplh có thể chọn đập cục đá bất kì. Nếu chọn cục thứ ~i~ và độ bền hiện tại của nó là ~D_i~ thì Ralph sẽ giảm độ bền của nó đi ~X~ giá trị. Nếu ban đầu ~D_i < X~ thì độ bền của cục đá sẽ trở về ~0~.
- Trong quá trình dán đá, Felix sẽ dán một cục đá. Nếu chọn cục thứ ~i~ và và độ bền hiện tại của nó là ~D_i~ thì Felix tăng độ bền của nó lên thành ~D_i + Y~. Felix không thể dán cục đá có độ bền hiện tại bằng ~0~.
- Trò chơi kéo dài ~999999999~ lượt. Nếu một người không thể đập-dán có thể bỏ lượt.
Bạn là Vanellope, người sẽ giúp Ralph tối đa hóa số lượng đá mà Ralph có thể đập mà Felix không dán được ở cuối trò chơi (Độ bền bằng ~0~). Đương nhiên Felix không muốn vậy. Số lượng đá mà Ralph có thể đập là bao nhiêu nếu cả hai đều chơi tối ưu?
Input
- Dòng thứ 1 chứa ba số nguyên ~n~, ~x~ và ~y~ (~0 \le n \le 1000~, ~1 \le x, y \le 1000~) lần lượt là số lượng đá và các tham số ~X~ và ~Y~.
- Dòng thứ 2 gồm ~n~ số nguyên ~D_1, D_2, \ldots, D_n~, (~0 \le D_i \le 900~), với ~D_i~ là độ bền ban đầu của viên thứ ~i~.
Output
Một số nguyên duy nhất là số đá mà Ralph đập được.
Sample
Input #1
3 4 5
1 2 3
Output #1
2
Hint
Có ~2~ trường hợp:
- Nếu ~x > y~ thì đáp án là ~n~ vì Ralph luôn luôn có thể làm giảm độ bền của cục đá và Felix không thể sửa kịp.
- Nếu ~x \le y~, Ralph cần đập ngay những cục đá có độ bền ~z \le x~; nếu không thì Felix sẽ dán nó khi đến lượt. Và vì các nước đi tối ưu, khi đến lượt Felix sẽ dán viên đá có độ bền ~z \le x~ bởi vì nếu không Ralph sẽ đập nó trong lượt kế tiếp.
Trong trường hợp này, Ralph sẽ bỏ qua những cục đá có độ bền ~z > x~ vì nếu đập thì Felix có thể sửa được ngay. Nên nếu ta tìm được ~n~ cục đá có độ bền ~z \le x~ thì đáp án sẽ là ~\lceil \frac{n}{2} \rceil~.
Problem source: CLB Lập Trình PTIT
Bình luận